Binary Search in Javascript

The binary search algorithm uses Divide and Conquer approach to search elements in a sorted array. It is one of the most efficient and fastest searching algorithms which helps you search for an element in a sorted array. It helps you to search for an element in an array in O(logn) time or logarithmic time.

Complete Working of Binary Search Algorithm

The first thing which is necessary for making the binary search algorithm work properly is to have the data collection or the array in sorted order.

• First of all you need to find the mid element from the array and check whether the mid element is equal to the element that needs to be searched or not. If it is then you need to return it.
• Otherwise, if it is less then the search element then search it from the start to the mid element.
• If it is greater then the middle element of the array then you need to search it from the mid to the last element.
• If the element is not found in the array then you need to simply return -1.

Binary Search in Javascript

Binary search works on the divide and conquer approach as it is very common to use recursive approach to implement it.

Input:
const result = search([-1,0,3,5,9,12],9);
console.log(result);

Output:
 4 //Element 9 is found at index 4

Code Snippet

Time Complexity : O(logn)

Space Complexity : O(n)

Duplicate elements 

If an array is having duplicate elements in it then it should ideally return the first element from the array. But the problem with binary search is that every time it doesn’t always return the first element.

Input:
const arr = [1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10];
console.log(binarySearch(arr, 5));
console.log(binarySearch(arr, 6));

Output:
5
6

From the array, it is clearly visible that element 5 is present in the 4th and 5th index but it is returning 5. But if we talk about the element 6 then it is present in the 6th and the 7th index but it returned 6.

In such a case you need to find the leftmost or the rightmost value from the collection which contains the duplicate values.

Finding the leftmost value using Binary Search

When finding the leftmost element from the duplicate elements in the array even if we have found the element in the collection. We generally have to keep looking in the lower range to get the first occurrence.

const leftMost = (arr, value, low = 0, high = arr.length - 1, result = -1) => {
  
  //Search if the array exists
  if(low <= high)  { 
    
    //Get the mid
    const mid = Math.ceil((low+high) / 2);  
    
    //If element found
    //Store the result
    //And the check the lower range to make sure we get the first occurrence
    if(value === arr[mid]){
      result = mid;
      return leftMost(arr, value, low, mid - 1, result);
    }
    
    //If value is less 
    //Then search in the lower range
    if(value < arr[mid]){
      return leftMost(arr, value, low, mid - 1, result);
    }else{
      //Else search in the upper range
      return leftMost(arr, value, mid + 1, high, result);
    }
  } 
  
  //In the end return the result
  return result;
}

Input:
const arr = [1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10];
console.log(leftMost(arr, 5));
console.log(leftMost(arr, 6));

Output:
4  //index of the first 5 in the array
6  //index of the first 6 in the array