Binary Search

The core idea of binary search is to halve the search space at each step.

1. Initialization: Create two pointers: left (pointing to the start of the array, index 0) and right (pointing to the end, arr.length - 1).
2. Loop: Continue searching as long as left is not greater than right.
3. Find the Middle: In each iteration, calculate the middle index: middle = Math.floor((left + right) / 2).
4. Comparison:
   • If arr[middle] is equal to the target element, you’ve found it! Return middle.
   • If arr[middle] is less than the target, the target can only be in the right half of the array. Move the left boundary: left = middle + 1.
   • If arr[middle] is greater than the target, the target is in the left half. Move the right boundary: right = middle - 1.
5. Termination: If the loop finishes and the element is not found, return -1.

const binarySearch = (arr, target) => {
  // Initialize pointers to the beginning and end of the array.
  let left = 0;
  let right = arr.length - 1;
 
  // Continue the loop as long as the left pointer is not to the right of the right pointer.
  // This condition means the search space is not yet empty.
  while (left <= right) {
    // Find the middle index.
    // Math.floor is used to round down to get a whole index.
    const middle = Math.floor((left + right) / 2);
    const guess = arr[middle];
 
    // Compare the middle element with the target value.
    if (guess === target) {
      // Element found! Return its index.
      return middle;
    }
 
    // If the middle element is less than the target,
    // the target can only be in the right half of the array.
    if (guess < target) {
      // Move the left search boundary to the right of the middle.
      left = middle + 1;
    } else {
      // Otherwise (the middle element is greater than the target),
      // the target can only be in the left half.
      // Move the right search boundary to the left of the middle.
      right = middle - 1;
    }
  }
 
  // If the loop has finished and the element was not found,
  // it means it is not in the array.
  return -1;
};

Solution Analysis:

• Time Complexity: O(log n). At each step, we reduce the search space by half, which makes this algorithm extremely fast for large arrays.
• Space Complexity: O(1). The algorithm uses only a few variables to store pointers, regardless of the input array size.
• Constraint: The main requirement is that the array must be sorted. If the array is not sorted, binary search will return an incorrect result or fail to find an existing element.