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]


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] <>< left="P,right="N,E)" left="0,right="P-1,E)" style="font-weight: bold;">2.Given an array A[1,...,N] such that A[1] < ..........

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 < middle="(left+right)/2;" style="font-weight: bold;">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