Binary Search Algorithm
Table Of Contents
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
andend
we now have to comparetarget
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
 By using
 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
Classic Recursive Binary Search
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;
}
Classic Iterative Binary Search
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 = mid1;
}
}
return 1;
}
Mid = Start + (End  Start)/2
// generally we write
mid = (start + end)/2
// instead write this way
mid = start + (endstart)/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 = mid1;
}
}
Order Agnostic Search
 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
 We are given an array
 Solution
 Find out the order of sorting by comparision first and last elements

arr[0]<arr[n1]
==> 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[n1]){return 1;}
if(arr[0]>arr[n1]){return 0;}
return 1;
}
First Last Occurence
 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)
 This can go on till first element, making it
 Go one step forward for last occurence

 This can go on till last element, making it
O(N)
 This can go on till last element, making it

 Go one step back for first occurence
 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
 Building on top of the previous approach which is still searching linearly we can implement BS on it again to optimize further down to
// 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 = mid1;
}
else if(nums[mid]<target){
start = mid+1;
}
else {
end = mid1;
}
}
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 = mid1;
}
}
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
 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 asX%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+n1)%n
because we donâ€™t want it to go out of bound, it will move back to desired places If
mid = n1
thennext = (n1+1)%n > 0
cycling back to the zereoth index  Similarly, if
mid=0
thenprev = (0+n1) > n1
cycling back to last index
 If
 This makes the
prevmidnext
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;
}
}
}