Binary Search:
Pre-condition:
- Array should be sorted.
Which problem addressed:
- To find if an element exists in that array or not. Return the index where element is present.
Time Complexity: O(logN)
int BinarySeaarch(int[] A,int len,int x){
int start=0; // start index of array A
int end=len-1; // end index of array A
while(start<=end){
int mid = (start+end)/2;
if(x == A[mid]) return mid;
else if(x<A[mid]) end =mid-1;
else start= mid+1;
}
return -1; // if not found element in array
}
Improvements:
The better way to calculate mid is:
mid = start + (end-start)/2
because if start and end are very high number then the sum of two higher value int can result in overflow.
Variances of Binary Search:
1) To find the occurrence of an element in a sorted array with duplicates.
int BinarySearch(int[] A,int len,int x){
int start = 0;
int end =len-1;
// this stores the index of first or last index of element x depending on code added with //*
int result =-1;
while(start<=end){
int mid = start +(end-start)/2;
if(a[mid] == x){
result = mid;
//* end = mid-1; // when we want to find first occurrence of element x;
//* start =mid+1; // when we want to find last occurrence of element x;
}else if(a[mid] > x){
end =mid-1;
}else
start =mid+1;
}
return result;
}
2) How many times sorted array is rotated.
Given a circularly sorted array with no duplicates.
The definition of rotation:
The number of elements before smallest element is equal to the number of rotations.
Thus the number of rotations is equal to the index of smallest element.
No of rotations = index of smallest element in array.
Note the variations applied to binary search:
int FindPivot(int[] a){
int len = a.length;
int lo = 0;
int hi = len-1;
if(len == 1) return 0;
if(len == 2){
return (a[0]>a[1])?1:0;
}
while(lo<=hi){
int mid = lo +(hi -lo)/2;
// the pivotal element will be lesser than its previous element
if(mid == 0 || a[mid]< a[mid-1]){
return mid;
}
if(a[mid] > a[0]){
lo = mid+1;
}else{
// may be element at mid can be minimum thus we set hi to mid
hi = mid;
}
}
// if array is sorted then first element is minimum
return a[0];
}
Note: This will work only if there is no duplicate elements in array.
If there are any duplicates then it can't be done in O(logn) .. it can be done linearly O(n).
