Mastering Binary Search: A Comprehensive Guide for Programmers

Binary search is a vital computer science algorithm widely used in various applications. The algorithm is an efficient way to search for a specific item in a sorted list of data. If you are a programmer, mastering binary search is a must-have skill. It helps to improve your performance, optimize your code, and solve complex programming problems. This comprehensive guide to mastering binary search is designed to give programmers a complete understanding of the algorithm. It covers the basics of binary search, implementation, applications, and advanced techniques.

This guide is suitable for both novice and experienced programmers who want to enhance their coding skills and tackle complex programming tasks. Whether you are a beginner or an expert, you will find this guide helpful in mastering this robust algorithm.

Understanding Binary Search

Binary search is the most efficient way to search for an element in a given ordered list. Generally, when we use a linear search, we need to check each element in a given list, and in the worst-case scenario, its time complexity can be O(n). But when the list is given in a sorted manner, we can reduce our time complexity to O(log n) by applying a Binary search.

The reason for reducing our time complexity is so efficient, as with each iteration we are cutting down half the search area. Searching elements becomes faster as the search area decreases.

Code Snippet

Before we understand how Binary search works, let us see the code first,

let binarySearch = (nums,target) => {
  let left = 0
  let right = nums.length - 1


  while(left <= right){
      let mid = left + Math.trunc((right - left) / 2)

      if(nums[mid] == target){
      	return mid
      }else if(nums[mid] < target){
      	left = mid + 1
      }else{
      	right = mid - 1
      }
   }
   
   return -1
}

Also read, Understanding Binary Search Trees with Js

Diagram

Also read, Simple Explanation on Sorting Algorithms with JavaScript | Part 1

Key Characteristics of Binary Search

left and right

We define two variables, let’s call them left and right. They will store array indexes and work like a boundary, such that we will only be looking at elements inside the perimeter. Normally, we would want to initialize the boundary to be the entire array.

Mid

The mid variable indicates the middle element within the boundary. It divides our border into two parts. 

In order to calculate the midpoint, you can add the left and right and divide it by two.

let mid = Math.trunc((left + right) / 2)

Note:- Calculating the midpoint using the above method fails at large values. Specifically, it fails if the sum of left and right is greater than the maximum positive value an integer data type can hold, (2³¹-1). This can cause overflow, so in order to avoid it, we need to calculate the midpoint like this: 

let mid = left + Math.trunc((right – left) / 2)

Comparing the target to the mid

We may determine which side of the boundary our target belongs on by comparing it to the mid. For instance, if our aim is higher than mid, it must be located to the right of mid. There is no reason to even keep track of all the numbers to the left in this situation. And maintaining the boundary’s shrinkage is the basic physics of binary search.

if(nums[mid] == target){
    return mid
}else if(nums[mid] < target){
    left = mid + 1
}else{
    right = mid - 1
}

Keep the loop going

Lastly, we use a while loop to keep the search going:

while (left <= right) { ... }

Time complexity analysis of the Binary Search

Binary Search is an efficient algorithm for searching in sorted arrays, with a time complexity of O(log n), making it much faster than linear search (O(n)) for large datasets.

Since the search range is halved at each step, the number of elements remaining in the search range reduces by half with every comparison. As a result, the number of comparisons required to find the target element is proportional to the logarithm of the number of elements ‘n’ in the array.

Mathematically, the number of steps required to reduce the search range to one element is log2(n). Hence, the time complexity of the binary search is O(log n).

However, binary search requires the array to be sorted, and its logarithmic time complexity is achieved through its divide-and-conquer strategy, reducing the search range by half in each iteration.

Also read, Simple Explanation of Sorting Algorithms with JavaScript | Part 2

Variations of Binary Search

Binary search can applied to a number of problems with slightly varying conditions and variable assignment. In order to master Binary Search, you have to also dive into its various variants and the number of problems that Binary Search can be used to solve.

Finding a Square root of a given number

Question

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

Link:- Leetcode

Examples

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Explanation

• We first check if x is 0 or 1. If it is, we know that the square root of 0 and 1 is 0 and 1 respectively, so we directly return x.

• For any other value of x, we set up a search range between 1 and x. We initialize two variables start and end to represent the range.
• Now comes the clever part: We use a while loop to repeatedly divide the search range in half (Binary Search) to find the square root.

• In each iteration of the loop, we calculate the middle value mid using the formula left + Math.trunc((right - left) / 2). This formula ensures that we don’t encounter any integer overflow when dealing with large values of x.

• Next, we calculate the square of mid and compare it with x.

• If the square of mid is greater than x, we know the square root lies in the lower half of the search range. So, we move the end pointer to the left to narrow down the search range.

• If the square of mid is equal to x, we have found the square root! So, we return mid as the answer.

• If the square of mid is less than x, we know the square root lies in the upper half of the search range. So, we move the start pointer to the right to continue the search.

• We repeat steps 4 to 8 until the start pointer becomes greater than the end pointer. At this point, we have found the floor value of the square root, and the end holds that value.

Code

var mySqrt = function(x) {
   let left = 1
   let right = x

   while(left <= right){
       let mid = left + Math.trunc((right-left)/2)

       if(mid*mid == x){
           return mid
       }else if(mid*mid > x){
           right = mid - 1
       }else{
           left = mid + 1
       }
   }
   return right
};

Also read, Introduction to Tree Data Structure

Index of First and Last occurrence of a given number

Question

Given an array of integer nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.

Link:- Leetcode

Examples

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Explanation

We have to return an array containing indexes of the given targets, having the first and last occurrence in the given array and if the target is not present then we return [-1,-1]. We will create two functions findPositionStart and findPositionEnd, to find respective indexes.

First Occurrence of the given Number

• findPositionStart(nums, target): This function finds the starting position of the target element in the sorted nums array.
• The function initializes two pointers, left and right, to the first and last indices of the array, respectively.
• It then enters a while loop to perform a binary search on the array until the left is greater than the right. Within each iteration, it calculates the mid-index using the formula left + Math.trunc((right - left) / 2).
• If nums[mid] is equal to the target, the target element has been found. In this case, it stores the mid index in the ans.
• It also narrows the search to the left half by updating right = mid - 1. This ensures that the leftmost occurrence of the target element is found.
• If nums[mid] is less than the target, the target element should be in the right half of the remaining search space. Therefore, it updates left = mid + 1.
• If nums[mid] is greater than the target, the target element should be in the left half of the remaining search space. So, it updates right = mid - 1.
• The function returns the ans variable, which will have the index of the starting position of the target element if it’s found; otherwise, it returns -1.

Last Occurrence of the given Number

• findPositionEnd(nums, target): This function finds the ending position of the target element in the sorted nums array.
• The function initializes two pointers, left and right, to the first and last indices of the array, respectively.
• It then enters a while loop to perform a binary search on the array until the left is greater than the right. Within each iteration, it calculates the mid-index using the formula left + Math.trunc((right - left) / 2).
• If nums[mid] is equal to the target, it means the target element has been found. In this case, it stores the mid index in the ans.
• It also narrows the search to the right half by updating left = mid + 1. This ensures that the rightmost occurrence of the target element is found.
• If nums[mid] is less than the target, the target element should be in the right half of the remaining search space. Therefore, it updates left = mid + 1.
• If nums[mid] is greater than the target, the target element should be in the left half of the remaining search space. So, it updates right = mid - 1.
• The function returns the ans variable, which will have the index of the starting position of the target element if it’s found; otherwise, it returns -1.

Code

let findPositionStart = (nums,target) => {
   let left = 0
   let right = nums.length - 1
   let ans = -1

   while(left <= right){
       let mid = left + Math.trunc((right - left) / 2)

       if(nums[mid] == target){
            ans = mid
            right = mid - 1
        }else if(nums[mid] < target){
            left = mid + 1
        }else{
            right = mid - 1
        }
   }

   return ans
}

let findPositionEnd = (nums,target) => {
   let left = 0
   let right = nums.length - 1
   let ans = -1

   while(left <= right){
       let mid = left + Math.trunc((right - left) / 2)

       if(nums[mid] == target){
            ans = mid
            left = mid + 1
        }else if(nums[mid] < target){
            left = mid + 1
        }else{
            right = mid - 1
        }
   }

   return ans
}

var searchRange = function(nums, target) {
    let res = [-1, -1]
    
    res[0]=findPositionStart(nums,target)
    res[1]=findPositionEnd(nums,target)
    
    return res
};

Also read, Introduction to Graph Data Structure

Floor and Ceil of a given number in the Sorted Array

Question

You’re given an unsorted array of n integers and an integer x. Find the floor and ceiling of x in arr[0..n-1].

The floor of x is the largest element in the array which is smaller than or equal to x. The ceiling of x is the smallest element in the array greater than or equal to x.

Examples

Input Format: n = 6, arr[] ={3, 4, 4, 7, 8, 10}, x= 5
Result: 4 7
Explanation: The floor of 5 in the array is 4, and the ceiling of 5 in the array is 7.

Explanation

We have to return an array containing the ceil and floor value of the given targets and if the target is not present then we return [-1,-1]. We will create two functions findFloor and findCeil, to find respective numbers.

Floor value of the given Number

• findFloor(nums, target): This function finds the floor of the target element in the sorted nums array.
• The function initializes two pointers, left and right, to the first and last indices of the array, respectively.
• It then enters a while loop to perform a binary search on the array until the left is greater than the right. Within each iteration, it calculates the mid-index using the formula left + Math.trunc((right - left) / 2).
• If nums[mid] is less than or equal to the target, the target element or a larger element is present on the left side of the current mid. In this case, it updates the ans variable to nums[mid] to store the current candidate for the floor and narrows the search to the left half by updating right = mid - 1.
• If nums[mid] is greater than the target, the target element or a smaller element is present on the right side of the current mid. Therefore, it updates left = mid + 1.
• The function returns the ans variable, which will have the index of the starting position of the target element if it’s found; otherwise, it returns -1.

Ceil value of the given Number

• findCeil(nums, target): This function finds the ceiling of the target element in the sorted nums array.
• The function initializes two pointers, left and right, to the first and last indices of the array, respectively.
• It then enters a while loop to perform a binary search on the array until the left is greater than the right. Within each iteration, it calculates the mid-index using the formula left + Math.trunc((right - left) / 2).
• If nums[mid] is less than or equal to the target, the target element or a larger element is present on the right side of the current mid. In this case, it updates the ans variable to nums[mid] to store the current candidate for the ceiling and narrows the search to the right half by updating left = mid + 1.
• If nums[mid] is greater than the target, the target element or a smaller element is present on the left side of the current mid. So, it updates right = mid - 1.
• The function returns the ans variable, which will have the index of the starting position of the target element if it’s found; otherwise, it returns -1.

Code

let findFloor = (nums,target) => {
  let left = 0
  let right = nums.length - 1
  let ans = -1


  while(left <= right){
      let mid = left + Math.trunc((right - left) / 2)

      if(nums[mid] <= target){
           ans = nums[mid]
           left = mid + 1
       }else{
       	   right = mid - 1
       }
   }
   
   return ans
}


let findCeil = (nums,target) => {
  let left = 0
  let right = nums.length - 1
  let ans = -1


  while(left <= right){
      let mid = left + Math.trunc((right - left) / 2)

      if(nums[mid] >= target){
           ans = nums[mid]
           right = mid - 1
       }else{
       	   left = mid + 1
       }
   }
   
   return ans
}


var searchRange = function(nums, target) {
   let res = [-1, -1]
  
   res[0]=findFloor(nums,target)
   res[1]=findCeil(nums,target)
  
   return res
};

Also read, Understanding Array, String, and Object Data Structure with JavaScript

Search in Rotated Sorted Array

Question

Given the array nums after the possible rotation and an integer target, return the index of the target if it is in nums, or -1 if it is not in nums.

Link:- Leetcode

Examples

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Explanation

Our function search takes two parameters, sorted array nums, and a target, which we want to find in a given array,

• It initializes two pointers, left and right, to keep track of the left and right boundaries of the search range. Initially, the left is set to 0 (the first index of the array), and the right is set to nums.length - 1 (the last index of the array).
• The code enters a while loop that runs as long as the left pointer is less than or equal to the right pointer.
• Inside the loop, it calculates the middle index, mid, using the formula left + Math.trunc((right - left) / 2). This helps in dividing the search range in half.
• It checks if the element at the middle index, nums[mid], is equal to the target. If it is, the function returns the mid as the index where the target is found.
• If the target is not found at the middle index, the code proceeds to check which side of the array is sorted (left or right) by comparing nums[left] with nums[mid].
• If nums[left] <= nums[mid], it means the left side of the array is sorted. In this case, it further checks if the target lies within this sorted range.
  • If it does (target is greater than or equal to nums[left] and less than or equal to nums[mid]), then the search range is restricted to the left side (right = mid - 1). Otherwise, the search range is shifted to the right side (left = mid + 1).
• If nums[left] > nums[mid], it means the right side of the array is sorted. In this case, it checks if the target lies within this sorted range.
  • If it does (target is greater than or equal to nums[mid] and less than or equal to nums[right]), then the search range is restricted to the right side (left = mid + 1). Otherwise, the search range is shifted to the left side (right = mid - 1).
• The loop continues to divide the search range until the target is found or until the left becomes greater than the right, which implies that the target is not present in the array.
• If the loop exits without finding the target, the function returns -1 to indicate that the target is not present in the array.

Code

var search = function(nums, target) {
    let left = 0
    let right = nums.length - 1

    while(left <= right){
        let mid = left + Math.trunc((right - left) / 2)
        
        if(nums[mid] == target){
            return mid
        }

        if(nums[left] <= nums[mid]){ // searching in left sorted side

            if(nums[left] <= target && target <= nums[mid]){
                right = mid - 1
            }else{
                left = mid + 1
            }
           
        }else{ // searching in right sorted side
            if(nums[mid] <= target && target <= nums[right]){
                left = mid + 1
            }else{
                right = mid - 1
            }
        }
    }

    return -1
};

Also read, What is Big O Notation – Space and Time Complexity

Koko Eating Bananas

Question

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hour.

Link:- Leetcode

Examples

Input: piles = [3,6,7,11], h = 8
Output: 4

Explanation

The given problem is to find the minimum eating speed (K) at which Koko can eat all the piles of bananas within a given number of hours (h).

• The minEatingSpeed function takes two parameters, piles (an array representing the number of bananas in each pile) and h (the maximum number of hours Koko has to eat all the bananas).
• It initializes two pointers, left and right, to search for the minimum eating speed. left is set to 1 (as the minimum eating speed cannot be zero or negative), and right is set to the maximum number of bananas in any pile (the upper limit of possible eating speeds).
• It also initializes the variable ans to keep track of the minimum eating speed found so far, starting with a value of Infinity.
• The code enters a while loop that runs as long as the left pointer is less than or equal to the right pointer.
• Inside the loop, it calculates the middle eating speed mid using the formula left + Math.trunc((right - left) / 2).
• It calls the calculateSpeed function with the current mid eating speed and the piles array to calculate the total hours required to eat all the bananas at this eating speed.
• The calculateSpeed function takes two parameters, k (eating speed) and piles (an array representing the number of bananas in each pile).
• It initializes a variable hour to keep track of the total hours required to eat all the bananas.
• The code then iterates through each pile of bananas in the piles array using a for loop.
• For each pile, it calculates the number of hours required to eat the bananas at the current eating speed k.
  • If the number of bananas in the pile (piles[i]) is divisible evenly by k, then the time taken to eat that pile is simply piles[i] / k hours.
  • Otherwise, it takes Math.trunc(piles[i] / k) + 1 hours, as Koko must take an extra hour to finish the remaining bananas.
  • The hour variable is updated with the calculated time for the current pile.
  • The function returns the total hours (hour) required to eat all the piles of bananas at the given eating speed (k).
• If the calculated hours are less than or equal to the given h (maximum hours Koko has), it means Koko can finish eating within the given time frame. In this case, it updates the ans variable with the current mid eating speed and then searches for lower eating speeds by updating right = mid - 1.
• If the calculated hours are greater than h, it means Koko cannot finish eating within the given time frame, and the eating speed needs to be increased. So, it updates left = mid + 1.
• The loop continues to search for the minimum eating speed until left becomes greater than right.
• Finally, the function returns the ans, which represents the minimum eating speed required for Koko to eat all the bananas within h hours.

Code

function calculateSpeed(k, piles){
    let hour = 0

    for(let i = 0; i < piles.length; i++){
        if(piles[i] % k == 0){
            hour+=Math.trunc(piles[i] / k)
        }else{
            hour+=Math.trunc(piles[i] / k) + 1
        }
    }
    return hour
}
var minEatingSpeed = function(piles, h) {
    let left = 1
    let right = Math.max(...piles)
    let ans = Infinity

    while(left <= right){
        let mid = left + Math.trunc((right - left) / 2)
        if(calculateSpeed(mid, piles) <= h){
            ans = mid
            right = mid - 1
        }else{
            left = mid + 1
        }
    }

    return ans
};

Also read, Simple Explanation on Searching Algorithms with JavaScript

Final Words

In conclusion, understanding binary search is essential for any programmer who wants to write efficient code. This guide provides a comprehensive overview of binary search, and with practice, you can apply it to various programming tasks.  

Following the steps outlined in this guide, you can implement binary search algorithms in your programs confidently and efficiently. A binary search is a powerful tool that helps reduce computing time, reduce memory usage, and improve overall performance. Whether you’re a beginner or an experienced programmer, mastering binary search will undoubtedly help you in your professional career. Try different variations of binary search, experiment, and see what works best for your specific use case. With practice, you will become a proficient binary search expert and improve your coding skills overall.