Implement Iterative binary search

Learn how to implement iterative binary search.

We have already seen in detail about the binary search and how to implement binary search recursively.

Iterative binary search

Binary search is a divide and conquer algorithm which finds a given an element in the sorted array.

How iterative binary search works?

• We get the middle element of the array and check if it is the element that we are searching for or not.
• If it is the element then return it, else.
• If the element that needs to searched is less than the middle element then we search the array again in lower range from middle. That is from start to middle - 1.
• If element is greater than middle element then we search in the upper range from middle + 1 till the last.
• Repeat this till all the elements in the array are searched. Else return -1.

const iterativeBS = (arr, value) => {
  //Get the low and high
  let low = 0;
  let high = arr.length - 1;
  
  //Loop till there elements needs to be searched in collection
  while(low <= high){
    //Get the mid
    let mid = Math.ceil((low + high) / 2);

    //If found return the index
    if(arr[mid] === value){
       return mid;
    }
    
    //If value is less
    //Then search in lower range
    if(value < arr[mid]){
      high = mid - 1;
    }else{
      //Else search in upper range
      low = mid + 1;
    }
  }
  
  //If not found return -1
  return -1;
}

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

Output:
6

Time complexity

After each operation the size of the array is reduced by half, so the mathematically time complexity for binary search is T(n) = T(n / 2) + c which when solved with recurrence relation or master theorem comes as O(logn).

Space complexity

We are using constant space so the space complexity is O(n).