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).