LeetCode-704: Binary Search

704. Binary Search

• Goal: Search for a target in a sorted array nums. Return its index, or -1 if not found.
• Constraint: Must achieve $O(log n)$ time complexity.

Example

1Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
2Output: 4

Quick Steps for Binary Search

Initial Setup

• Set left = 0, right = nums.length - 1.

Middle Calculation

• Compute mid = Math.floor((left + right) / 2).

Comparison

• If nums[mid] == target: Return mid.
• If nums[mid] < target: Move left to mid + 1.
• If nums[mid] > target: Move right to mid - 1.

Repeat

• Continue until left > right.

Return

• If found, return the index; else, return -1.

JavaScript Implementation

 1/**
 2 * @param {number[]} nums
 3 * @param {number} target
 4 * @return {number}
 5 */
 6var search = function (nums, target) {
 7    let N = nums.length;
 8    let l = 0;
 9    let r = N - 1;
10    let mid = 0;
11
12    while (l <= r) {
13        mid = Math.floor((r + l) / 2);
14
15        if (nums[mid] === target) return mid;
16        if (nums[mid] < target) {
17            l = mid + 1;
18        } else {
19            r = mid - 1;
20        }
21    }
22
23    return -1;
24};

Summary

• Binary Search: Divide and conquer by halving the search space.
• Key Points: Efficiently narrows down the search to find the target in $O(log n)$ time.

References

• 74. Search a 2D Matrix