What is the time complexity of Binary Search?

The time complexity of Binary Search is O(log n), as the search space is halved with each iteration.

Can Binary Search be used on an unsorted array?

No, Binary Search requires the array to be sorted in either ascending or descending order.

How do I handle edge cases in the Binary Search problem?

Edge cases include situations where the target is not found. In such cases, ensure to return -1 after exhausting the search space.

What are some variants of the Binary Search problem?

Variants include searching in a descending sorted array, finding the first occurrence of a target in a duplicate array, or searching for the closest value to the target.

How does GhostInterview help with Binary Search problems?

GhostInterview provides structured hints, solution explanations, and potential pitfalls, ensuring you're well-prepared for solving Binary Search in interviews.

#704

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target ，如果 target 存在返回下标，否则返回 -1 。你必须编写一个具有 O(log n) 时间复杂度的算法。示例 1: 输入: nums = [-1,0,3,5,9…

数组二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

lightbulb

解题思路

方法一：二分查找

我们定义二分查找的左边界 $l=0$ ，右边界 $r=n-1$ 。

每一次循环，我们计算中间位置 $\textit{mid}=(l+r)/2$ ，然后比较 $\textit{nums}[\textit{mid}]$ 和 $\textit{target}$ 的大小。

如果 $\textit{nums}[\textit{mid}] \geq \textit{target}$ ，说明 $\textit{target}$ 在左半部分，我们将右边界 $r$ 移动到 $\textit{mid}$ ；
否则，说明 $\textit{target}$ 在右半部分，我们将左边界 $l$ 移动到 $\textit{mid}+1$ 。

循环结束的条件是 $l<r$ ，此时 $\textit{nums}[l]$ 就是我们要找的目标值，如果 $\textit{nums}[l]=\textit{target}$ ，返回 $l$ ，否则返回 $-1$ 。

时间复杂度 $O(\log n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l if nums[l] == target else -1

speed

复杂度分析

指标	值
时间	O(\log n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently explain how binary search works and its time complexity?
question_mark
Does the candidate implement the binary search algorithm correctly without unnecessary computations?
question_mark
Does the candidate handle edge cases, such as when the target is not present, effectively?

warning

常见陷阱

外企场景

error
Misunderstanding the search space boundaries; incorrect pointer updates may lead to infinite loops or missing the correct index.
error
Not properly handling the case when the target is not found, leading to incorrect return values.
error
Overcomplicating the solution by adding unnecessary checks or conditions that don't affect the binary search logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Search for the target value in a descending sorted array.
arrow_right_alt
Find the first occurrence of the target if there are duplicates.
arrow_right_alt
Implement a binary search that finds the closest value to the target when it’s not present.

help

常见问题

外企场景

继续练习

#710 黑名单中的随机数 #713 乘积小于 K 的子数组 #718 最长重复子数组