Coding Interview Questions | Binary Search

December 17th, 2023

Introduction:

This summary will talk about my solution to the binary search problem as seen on leetcode here.

Solution:

function search(nums: number[], target: number): number {
  let leftIdx = 0;
  let rightIdx = nums.length - 1;

  while (leftIdx <= rightIdx) {
    const middleIdx = Math.floor((rightIdx + leftIdx) / 2);
    const valAtMiddleIdx = nums[middleIdx];

    if (valAtMiddleIdx === target) {
      return middleIdx;
    }

    if (valAtMiddleIdx > target) {
      rightIdx = middleIdx - 1;
    }

    if (valAtMiddleIdx < target) {
      leftIdx = middleIdx + 1;
    }
  }

  return -1;
}

Summary:

• The function above initializes two pointers, leftIdx and rightIdx, representing the current search space. leftIdx is initialized to 0, and rightIdx is initialized to the last index of the array (nums.length - 1).

• We then iteratively search for the target within the current search space (leftIdx to rightIdx). The loop continues as long as leftIdx is less than or equal to rightIdx.

• Inside the loop, the middle index is calculated using Math.floor((rightIdx + leftIdx)/2).

• The value at the middle index is compared with the target, and the search space is updated accordingly. If the value at the middle index is equal to the target, the function returns the middle index. If the value is greater, the rightIdx is updated to middleIdx - 1 to search in the left half. If the value is less, the leftIdx is updated to middleIdx + 1 to search in the right half.

• If the target is not found within the while loop, the function returns -1, indicating that the target is not present in the array.

The function implements a binary search on the sorted input array of nums and thus has a time complexity of O(log n).