Binary search

Binary Search



1. Given an array which is sorted but the sequence of sorted elements not necessarily starting from the first position which means you were given an array which is of the form [Ak+1 Ak+2,......An,A1,A2,............Ak]where A[1] <A[2] < .......... <A[N] find whether a given element E is present or not?


Solution: The only difference between a normal binary search and this problem is that the sorted array might start somewhere in the middle of the array.

We solve this problem in 2 steps.
step1:find the position P from which the array starts

Explanation:

int findstart(A,int left,int right)
{
int middle=(left+right)/2;

if(A[left] < A[middle] < A[right]) // the array is in sorted order
{
return left;
}

else if(A[right] <A[left] <A[middle]) // the left portion is in order
{
return findstart(A,middle+1,right);
}

else // the right portion is in order
return findstart(A,left,middle-1);
}


step2:Search in a subarray of the given array for the element E.


if we know the position p of the smallest element in the array say ,
then
if P=0 then it is in no respect different from the normal binary search.

otherwise we can partition the given array A in to 2 subarrays A(0,..,P-1)
and A(P,...,N).


Now if given key E < A[N] then call binarysearch(A,left=P,right=N,E)
else call binarysearch(A,left=0,right=P-1,E)







2.Given an array A[1,...,N] such that A[1] <A[2] < .......... <A[N].
find a position i such that A[i]=i.

Sol: This just uses a flavor of binarysearch.
Initial search space of i is [1,2,.....,N]

Here goes the algorithm.
int Search (int A[], int left, int right)

{

If(left < right)
return -1 (indicates that there is no i such that A[i]=i.

else
{
Middle=(left+right)/2;

if(A[Middle] == Middle)
then return Middle;

else if(A[Middle] < Middle)

return Search(A,left,Middle-1);

else
return Search(A,Middle+1,right);
}

}






3.Given 2 sorted arrays A and B each of size N,find the combined median of A and B?

Sol:Let A[i] denote "i" th element in A and B[i] be the corresponding in B (1 <= i <= N)
The combined median of A and B will have N elements to its left and N-1 elements to its right in the combined sorted union of A and B.
We shall use this fact to solve this question.
if A[i] is the median, then there should be N-i elements in B less than it and the rest more .
So it amounts to saying that A[i] falls between B[N-i] and B[N-i+1].

If B[N-i] <= A[i] <= B[N-i+1] then A[i] is the combined median.

else if A[i] < B[N-1] then the combined median if it at all belongs to A will be to the left of A[i].

else the combined median if it at all belongs to A will be to the right of A[i].


The border cases of i=1 and i=N can be properly manages with out much fuss.

So the initial search space of i for the above procedure will be [1,2,.........,N].

We can employ a flavor of binary search in choosing i in each iteration where in the above procedure is employed.

1)We start with i=N/2 .

begin
2) if B[N-i] <= A[i] <= B[N-i+1] then A[i] is the combined median.
3) else if A[i] < B[N-1] then the search space of i is [1,2,...,N/2 -1] and goto step2
4) else the search space of i is [N/2 +1,....,N] and goto step2

end

Hence using the above procedure if the median belongs to A can be determined in log(N) (binary searching for i)