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;
}


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


// 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;
    		}
	}
}

Notes mentioning this note