# Binary Search Algorithm

## Theory & Workings

### Intution Behind Algorithm

• `Seach space` : The space where the binary seach is being performed
• In each step half the searcch space using the property that the elements are already sorted

### How Algorithm works

• How it finds
• By using `start` `mid` and `end` we now have to compare `target` with these
• If the target value isnâ€™t in a range, we can happily discard the other half
• Essentially halfing the array in each step
• What each step means
• `start < end`
• There is still search space left there the target could be present
• `start == end`
• We have reached the possible position, if the element were to be present it has to be in this location or not
• `start > end`
• We have exhausted the search scope of this problem

### Time Complexity

• `Log(N)`
• As in each step we are reducing the seach space
• `n + n/2 + n/4 + n/8 + .. ... ....`

## Implementation

``````
int findnum(int arr[], int low, int high, int target) {
if (high >= low) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] > target) {
return findnum(arr, low, mid - 1, x);
}
else if (arr[mid] < target) {
return findnum(arr, mid + 1, high, x);
}
}
return -1;
}

``````
• As seen in
``````int binarysearch(vector<int> nums, int target){
int start = 0;
int end = nums.size()-1;

while(start<=end){
int mid=(start+end)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
start = mid+1;
}
else (nums[mid]>target){
end = mid-1;
}
}
return -1;
}

``````

### Mid = Start + (End - Start)/2

``````
// generally we write
mid = (start + end)/2

// instead write this way
mid = start + (end-start)/2

// why do this
// 1. avoids integer overflow
// 2. makes you look cool and fancy

``````

## Variations

### Array is sorted in Reverse order

• Question
• Approach
• Flip the search space
``````
// everything remains the same
// we are only changing the search space

// Question : nums = [58,45,32,12,11,3] target=45
// start = 0, end = 5, mid = 2

// after comparing 45 with 32 with nums[2]
// our search space should be on left even though nums[mid]<target

// hence flip the search space

while(start<=end){
int mid=(start+end)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
end = mid+1;
}
else (nums[mid]>target){
start = mid-1;
}
}
``````
• Problem
• We are given an array `nums` that is sorted but the order of sorting is not given to use
• `nums` can be sorted in either asc or dec order
• Implement BS on nums
• Solution
• Find out the order of sorting by comparision first and last elements
• `arr[0]<arr[n-1]` ==> ascending
``````
// fist and second element can be same in some cases where duplicates are allowed
// so we need can directly check for first and last element

// this function returns __ for __ case
// 0 dec
// 1 asc
// -1 all equal

bool check(vector<int> nums, int n){
if(arr[0]<arr[n-1]){return 1;}
if(arr[0]>arr[n-1]){return 0;}
return -1;
}
``````

### First Last Occurence

• First and last occurrences of X - GeeksforGeeks

• Naive Iterative approach
• Simplest way will be to start from start and go unitl the very end storing the first and last occurences
• Slightly better
• Find the element using Class BS and the use a loop check until newer element is found
• `[2,3,4,4,4,5,6]` in this classsic bs will give 3 index
• Go one step back for first occurence
• This can go on till first element, making it `O(N)`
• Go one step forward for last occurence
• This can go on till last element, making it `O(N)`
• BS Implementation
• Building on top of the previous approach which is still searching linearly we can implement BS on it again to optimize further down to `O(logN)`
• Here we are still continuing the search even after finding the elemnt as it can be persent in the other indexes as well.
• Search space is still present after each iteration
``````
// slightly better one
// mid -> value returned by BS

temp = mid
while(temp>=0 && arr[temp]==arr[mid]){
mid=temp;
temp--;
}

// Optimizing BS
// continuing with binary search

// 1st occurence
int res = -1;
while(start<=end){
int mid=(start+end)/2;
if(nums[mid]==target){
res = mid;
end = mid-1;
}
else if(nums[mid]<target){
start = mid+1;
}
else {
end = mid-1;
}
}
return res;

// last occurence
int res = -1;
while(start<=end){
int mid=(start+end)/2;
if(nums[mid]==target){
res = mid;
start = mid+1;
}
else if(nums[mid]<target){
start = mid+1;
}
else {
end = mid-1;
}
}
return res;

``````

### Count the frequencey in Sorted Array

• Intution
• Making use of the property of sorted array that makes the all the elements appear together
``````
// Intution
// Making use of the property of sorted array that makes the all the elements appear together

// defualt functions

int main () {
vector<int> v{1, 2, 3, 3, 3, 4};
cout << upper_bound(v.begin(), v.end(), 3) - lower_bound(v.begin(), v.end(), 3);
}

// using 1st and last occurences

int first = firstOccurence(v,3);
int last = lastOccurence(v,3);
cout << last - first + 1;

// adding one to fix the offset

``````

### No of time Sorted Array is Rotated

• GFG-mininum-number-in-a-sorted-rotated-array

• Pivot is the element through which the array is sorted
• The no of times the array is sorted is X is then the pattern repeats after some time
• `0-[1,2,3] -> 1-[2,3,1] -> 2-[3,1,2] -> 3-[1,2,3]`
• Pattern for `X` is same as `X%N` where N is the size of array
• Intution
• We need to find out if the middle element is smallest element or not
• To achieve this we need (2) things
• (1) A way to figure out if the current mid is actually the smallest element
• (2) A way to decide where to move in the next iteration of alogrithm
• Approach
• (1) the current element is the smallest iff itâ€™s smaller than both of its neighbours
• (2) Check which part (left or right) is sorted and continue search in unsorted part
• Implementation
• `prev - mid - next` occur in order of the array
• `(mid+1)%n (mid+n-1)%n` because we donâ€™t want it to go out of bound, it will move back to desired places
• If `mid = n-1` then `next = (n-1+1)%n --> 0` cycling back to the zereoth index
• Similarly, if `mid=0` then `prev = (0+n-1) --> n-1` cycling back to last index
• This makes the `prev-mid-next` trio to work as in rotating cyclic for array
``````
int findKRotation(int arr[], int n) {
int low = 0, high = n - 1;
while (low <= high) {

int mid = low + (high - low) / 2;
int next = (mid + 1) % n;
int prev = (mid + n - 1) % n;

// 6 5 [1] 2 3
if (arr[mid] <= arr[prev] && arr[mid] <= arr[next]) {
return mid;
}
// 5 1 [2] 3 4
else if (arr[mid] <= arr[high]) {
high = mid - 1;
}
// 2 3 [4] 5 1
else {
low = mid + 1;
}
}
}

``````