Binary search algorithm

Binary search

The binary search algorithm is used in a sorted array by repeatedly dividing search items in half.

In binary search, the search space is reduced in each step where the sub-problem is roughly half the original size. The binary search is also called the decrease and conquer algorithm as search space is reduced in each step.

In binary search, the sub-problem can be solved using iterative or recursive approaches. Following is the recursive approach for solving binary search in JavaScript:

Binary search with recursion:

   const arr = [1, 7, 9, 23, 25];
   let start = 0;
   let end = arr.length - 1;
   const target = 8 ;

   function binarySearch(arr, start, end, target) {
       if(start > end) return false;

       const mid = Math.floor((end + start) / 2);
       console.log('mid is: ', mid, 'start: ', start, 'end: ', end);
       if(arr[mid] === target) return true;

       if (arr[mid] > target) {
           return binarySearch(arr, start, mid - 1 , target);
       } else {
           return binarySearch(arr, mid + 1, end, target);
       }
   }

   console.log(binarySearch(arr, start, end, target)); // false

Binary search with iterative approach:

const binarySearch = (array, target) => {
    let start = 0;
    let end = array.length - 1;

    while (start <= end) {
        const mid = Math.floor(( end + start ) / 2); 
        console.log('Mid: ', mid);
        if (target === array[mid]) {
            return true;
        } else if ( target > array[mid]) {
            start  = mid + 1; 
        } else {
            end = mid - 1;
        }
    }

    return false; 
}
 
const arr = [1, 7, 9, 23, 25];
console.log(binarySearch(arr, 23)); // true

Binary search complexity:

Let us consider we have an array of length n. On each iteration, the array size becomes half. For example:

On the first iteration:

array length = n

On the second iteration:

array length = n/2

On the third iteration:

array length = (n/2)/2 = n/22

.
.
.
On the k^th iteration:

array length = n/2k

If it takes k^th iteration to find the element in the array, at k^th iteration the array length becomes 1. So, we can write this:

array length = n/2k = 1
2k = n

Now apply log function on both sides: