Java Reference
In-Depth Information
/
**
@returnThepositionofanelementinsortedarrayA
withvaluek.IfkisnotinA,returnA.length.
*
/
staticintbinary(int[]A,intk){
intl=-1;
intr=A.length; //landrarebeyondarraybounds
while(l+1!=r){//Stopwhenlandrmeet
inti=(l+r)/2;//Checkmiddleofremainingsubarray
if(k<A[i])r=i; //Inlefthalf
if(k==A[i])returni;//Foundit
if(k>A[i])l=i; //Inrighthalf
}
returnA.length; //SearchvaluenotinA
}
Figure3.5
Implementation for binary search.
If we expand the recurrence, we find that we can do so only log n times before
we reach the base case, and each expansion adds one to the cost. Thus, the closed-
form solution for the recurrence is T(n) = log n.
Function
binary
is designed to find the (single) occurrence of K and return
its position. A special value is returned if K does not appear in the array. This
algorithm can be modified to implement variations such as returning the position
of the first occurrence of K in the array if multiple occurrences are allowed, and
returning the position of the greatest value less than K when K is not in the array.
Comparing sequential search to binary search, we see that as n grows, the (n)
running time for sequential search in the average and worst cases quickly becomes
much greater than the (log n) running time for binary search. Taken in isolation,
binary search appears to be much more efficient than sequential search. This is
despite the fact that the constant factor for binary search is greater than that for
sequential search, because the calculation for the next search position in binary
search is more expensive than just incrementing the current position, as sequential
search does.
Note however that the running time for sequential search will be roughly the
same regardless of whether or not the array values are stored in order. In contrast,
binary search requires that the array values be ordered from lowest to highest. De-
pending on the context in which binary search is to be used, this requirement for a
sorted array could be detrimental to the running time of a complete program, be-
cause maintaining the values in sorted order requires to greater cost when inserting
new elements into the array. This is an example of a tradeoff between the advan-
tage of binary search during search and the disadvantage related to maintaining a
sorted array. Only in the context of the complete problem to be solved can we know
whether the advantage outweighs the disadvantage.
