Binary Search with JavaScript

Binary Search is one of the most intuitive and optimal algorithms for finding an element in a sorted array.

A quick look at binary search

1. To implement binary search, the array must be sorted
2. Much Faster than linear search.
3. Has a time complexity of O(logN).
4. Rather than eliminating one element at a time, it can eliminate half of the remaining elements at a time.

Execution Methodology :
Binary search algorithm makes use of the "Divide and Conquer" approach.

Binary Search pseudocode:

1. This function accepts a sorted array and a value.
2. Create a left pointer at the start of the array, and a right *pointer at the end of the array.
3. 0 index is the left pointer and the end of the array is the right pointer.
4. Pick a middle pointer. Typically, an average of the left and right pointer. If the middle point is a fraction number, we round it up or floor it down.

5. While the left pointer comes before the right pointer:
   a) Create a pointer in the middle.
   b) If you find the value you want, return the index.
   c) If the value is too small, move the left pointer up.
   d) If the value is too large, move the right pointer down.

6. If you never find the value, return -1

Code in JavaScript :

function binarySearch(arr, value) {
  // setting the lest pointer at the start of the array
  let left = 0;
  // setting the left pointer at the end of the array
  let right = arr.length - 1;
  // picking the middle of the array for even and odd number of elements
  let mid = Math.floor((left + right) / 2);
  while (left <= right) {
    //   If the value is too small, move the left pointer up.
    if (arr[mid] < value) {
      left = mid + 1;
      mid = Math.floor((left + right) / 2);
    }
    // If the value is too large, move the right pointer down.
    else if (arr[mid] > value) {
      right = mid - 1;
      mid = Math.floor((left + right) / 2);
    } else {
      return mid;
    }
  }

  // If you never find the value , return -1
  return -1;
}

console.log(binarySearch( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,], 15)); // returns 14

console.log(binarySearch([2,6,25,89,100,110,120,127,150],2)); //returns 0