LeetCode 704: Binary Search (Classic Interval Halving)

2026-03-12 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 704ArrayBinary Search

Today we solve LeetCode 704 - Binary Search.

Source: https://leetcode.com/problems/binary-search/

English

Problem Summary

Given a sorted integer array nums (ascending) and an integer target, return the index of target if found; otherwise return -1.

Key Insight

Because the array is sorted, each comparison at mid lets us discard half of the search space. This gives logarithmic time complexity.

Brute Force and Limitations

Linear scan checks every element from left to right. It is simple but costs O(n), which is unnecessary for sorted input.

Optimal Algorithm Steps

1) Initialize left = 0, right = n - 1.
2) While left <= right, compute mid = left + (right - left) / 2.
3) If nums[mid] == target, return mid.
4) If nums[mid] < target, move left = mid + 1.
5) Otherwise move right = mid - 1.
6) If loop ends, return -1.

Complexity Analysis

Time: O(log n).
Space: O(1).

Common Pitfalls

- Using while (left < right) with closed interval updates and missing the final candidate.
- Mid overflow in some languages when using (left + right) / 2 directly.
- Mixing interval conventions ([left, right] vs [left, right)) inconsistently.
- Forgetting to return -1 when not found.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }

        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

var search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;

    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
};

中文

题目概述

给定一个升序整数数组 nums 和目标值 target，若目标值存在则返回下标，否则返回 -1。

核心思路

数组有序意味着每次比较中点后，都能排除一半区间，因此可以用二分查找把复杂度从线性降到对数级。

暴力解法与不足

暴力法从左到右逐个比对，时间复杂度 O(n)。在有序数组场景下，这个做法没有利用有序性。

最优算法步骤

1）初始化闭区间边界 left = 0、right = n - 1。
2）循环条件为 left <= right，计算中点 mid。
3）若 nums[mid] == target，直接返回。
4）若 nums[mid] < target，说明目标在右半区，更新 left = mid + 1。
5）否则目标在左半区，更新 right = mid - 1。
6）循环结束仍未命中则返回 -1。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 区间定义与更新不一致（闭区间写法却套用开区间更新）。
- 中点计算可能溢出，建议使用 left + (right - left) / 2。
- 循环条件写成 left < right 导致漏查最后一个元素。
- 未命中时忘记返回 -1。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }

        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

var search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;

    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
};