704. Binary Search

At a Glance

• Topic: Binary Search
• Pattern: Binary Search
• Difficulty: Easy
• LeetCode: 704

Problem Statement

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

Approach & Solution Steps

Use a standard binary search approach with left and right pointers. Calculate the mid index, compare the mid value with the target, and narrow down the search space accordingly.

Optimal JS Solution

function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.