Scribd
Upload
80 views

Binary Search Algorithm

The document describes the divide-and-conquer paradigm for algorithm design. It breaks problems into smaller subproblems, solves the subproblems recursively, and then combines the solutions to solve the original problem. Binary search is provided as a simple example that divides the search space in half at each step until finding the target value. Sequential search is contrasted as checking each element sequentially until the target is found. Binary search runs in logarithmic time while sequential search runs in linear time on average.

Uploaded by

Salman Ahmed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
80 views

Binary Search Algorithm

The document describes the divide-and-conquer paradigm for algorithm design. It breaks problems into smaller subproblems, solves the subproblems recursively, and then combines the solutions to solve the original problem. Binary search is provided as a simple example that divides the search space in half at each step until finding the target value. Sequential search is contrasted as checking each element sequentially until the target is found. Binary search runs in logarithmic time while sequential search runs in linear time on average.

Uploaded by

Salman Ahmed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

Divide-and-conquer Paradigm.

>> top-down technique to design algorithms.


>> the approach divides the problem into smaller subproblems that are simpler to
solve, and
>> then composing the partial solutions into the solution of the original proble
m.
Formally, the major phases are:
>> Breaking the problem into several sub-problems that are similar to the origin
al problem but smaller in size,
>> Solve the sub-problem recursively (successively and independently), and then
>> Combine these solutions to subproblems to create a solution to the original p
roblem.
Binary Search.
>> simplest application.
>> extremely well-known instance of divide-and-conquer paradigm.
Basic Idea.
Given an ordered array of n elements,
>> "probe" the middle element of the array.
>> continue in either the lower or upper segment of the array, depending on the
outcome of the probe until we reached the required (given) element.
Assumption. A[1 ... n] be an array of non-decreasing sorted order; that is A [i]
<=A [j] whenever 1<=i<=j<=n.
Problem Statement.
Let 'q' be the query point. The problem consist of finding 'q' in the array A. I
f q is not in A, then find the position where 'q' might be inserted.
Formally, find the index i such that 1 <= i <= n+1 and A[i-1] < x <= A[i].
Sequential Search.
Look sequentially at each element of A until either we reach at the end of an ar
ray A or find an item no smaller than 'q'.
Pseudocode. Sequential search for 'q' in array A.
FOR i = 1 to n DO
IF A[i] >= q THEN
return index i
END IF
return n + 1
END FOR
Analysis.
T(n) = ?(r), where r is the index returned.
Worst case. O(n)
Average case. ?(n) ; 'q' is indeed in the array, takes (n+1)/2 on average
Best case. O(1)
Binary Search.
Look for 'q' either in the first half or in the second half of the array A.
Idea.
Compare 'q' to an element in the middle, n/2 , of the array. Let k = n/2.
If q <= A[k], then search in the A[1 . . . k];
Otherwise search T[k+1 . . n] for 'q'.
Pseudocode.
IF i == j THEN return index i (end case)
k = (i + j)/2
IF q <= A [k] THEN
return BinarySearch ( A[i ... k], q )
ELSE
return BinarySearch ( A[k+1 ... j, q )
END IF
Analysis.
T(n) = O(log n)
Iterative Binary Search.
Search for q in array A[1 . . n]
IF q > A[n] THEN return n + 1 ;end case
i = 1;
j = n;
WHILE i < j DO
k = (i + j)/2
IF q = A [k] THEN
j = k
ELSE
i = k + 1
END IF
END WHILE
return index i
Analysis.
T(n) = ?(log n) ; identical to recursive version

You might also like