💬 Discord
Sign In
NeetCode #260LC-704EasyBinary SearchNC 150NC 250
← Back to All Problems

#260 · #704 · Binary Search(二分查找)

📌 Problem Statement & Constraints

Given a sorted array of integers nums and an integer target, return the index of target if it exists, otherwise -1. Constraints: 1 <= nums.length <= 10^4, -10^4 < nums[i], target < 10^4, all values are distinct.

💡 Core Algorithmic Approaches

  1. Maintain the invariant that the answer, if it exists, lies in [lo, hi].
  2. Compare the middle element with the target and discard the half that cannot contain it.
  3. Use lo <= hi as the loop condition for the classic inclusive-bounds formulation.
  4. Be consistent: lo = mid + 1 / hi = mid - 1 with while lo <= hi, or lo = mid + 1 / hi = mid with while lo < hi. Mixing the two is the source of most off-by-one bugs.

💻 Benchmark Python3 Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:                # inclusive bounds
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): the search space halves each iteration.
💾 Space Complexity
O(1): three indices.

⚠️ Interview Pitfalls & Follow-ups

  • Mixing the two loop-condition conventions: while lo < hi with hi = mid - 1 can skip the answer; pick one convention and stay consistent.
  • Using mid = (lo + hi + 1) // 2 with the inclusive form: the upper-bias variant is for the "find the last valid" pattern, not for plain lookup.
  • Overflow in lo + hi: a real concern in Java/C++; Python's unbounded integers make it moot, but lo + (hi - lo) // 2 is the portable idiom.
  • Assuming the array may contain duplicates: this problem guarantees distinct values; with duplicates you would need lower/upper bound variants.