二分查找面试题总结：左右边界、答案二分与 Java 模板

二分查找最容易让人翻车的地方不是思想，而是边界。left、right、mid、循环条件、返回值，只要有一个含义没想清楚，就很容易写出死循环或者漏掉答案。

left

right

mid

面试里判断能不能用二分，先看一句话：答案所在空间是否有单调性。数组有序只是最直观的一种情况，最小速度、最小容量、最小天数这类题，也可以在答案范围上二分。

面试考察重点

面试考察重点

能写出基础二分模板。

能处理左边界、右边界。

能识别答案二分，而不是只会在数组里找数。

能解释为什么循环会结束，为什么不会漏答案。

能说出时间复杂度是 O(logn)，空间复杂度通常是 O(1)。

O(logn)

O(1)

什么时候想到二分？

什么时候想到二分？

不要把二分查找理解成“只能在有序数组里找数字”。它真正依赖的是 单调性。

常见单调性有两类：

类型例子判断方式数组单调有序数组中找 targetnums[mid] 和 target 比较后能排除一半答案单调求最小速度、最小容量、最少天数某个答案可行时，更大的答案也可行，或反过来

类型例子判断方式

类型

例子

判断方式

数组单调有序数组中找 targetnums[mid] 和 target 比较后能排除一半

数组单调

有序数组中找 target

target

nums[mid] 和 target 比较后能排除一半

nums[mid]

target

答案单调求最小速度、最小容量、最少天数某个答案可行时，更大的答案也可行，或反过来

答案单调

求最小速度、最小容量、最少天数

某个答案可行时，更大的答案也可行，或反过来

比如“爱吃香蕉的珂珂”里，吃香蕉速度越快，越容易在规定时间内吃完。这里数组本身不需要有序，单调的是“速度”和“是否能吃完”之间的关系。

面试时可以这样判断：

题目是否在找一个位置、边界或最小/最大可行值？

如果猜一个答案 x，能不能在 O(n) 或更低复杂度内判断它是否可行？

x

O(n)

x 变大或变小时，可行性是否单调变化？

x

三个问题都能回答上来，基本就可以尝试二分。

基础二分模板

基础二分模板

适合在有序数组中查找一个确定值：

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

这个模板里，搜索区间是闭区间 [left, right]，所以循环条件是 left <= right。每次排除 mid，因此更新成 mid + 1 或 mid - 1。

[left, right]

left <= right

mid

mid + 1

mid - 1

用一句话记这个模板：区间里每个位置都还可能是答案，循环结束时区间为空。

举个例子，数组 [1, 3, 5, 7, 9] 中找 7：

[1, 3, 5, 7, 9]

7

left = 0，right = 4，mid = 2，nums[mid] = 5，目标在右侧。

left = 0

right = 4

mid = 2

nums[mid] = 5

更新 left = mid + 1 = 3。

left = mid + 1 = 3

mid = 3，找到 7。

mid = 3

7

如果查找 6，最后会出现 left > right，说明闭区间已经被排空，返回 -1。

6

left > right

-1

左边界模板

左边界模板

找第一个大于等于 target 的位置：

target

int lowerBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int lowerBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

这个模板的搜索区间是左闭右开 [left, right)。right 初始化为 nums.length，返回值可能等于 nums.length，表示数组中不存在大于等于 target 的位置。

[left, right)

right

nums.length

nums.length

target

左边界模板的关键不是“找到 target”，而是“找到第一个满足条件的位置”。这个写法能自然处理目标不存在的情况。

比如数组 [1, 2, 2, 2, 4]，找第一个大于等于 2 的位置：

[1, 2, 2, 2, 4]

2

当 nums[mid] >= 2，mid 可能就是答案，所以不能排除 mid，更新 right = mid。

nums[mid] >= 2

mid

mid

right = mid

当 nums[mid] < 2，mid 和它左边都不可能是答案，更新 left = mid + 1。

nums[mid] < 2

mid

left = mid + 1

循环结束时，left == right，这个位置就是第一个满足条件的位置。

left == right

右边界模板

右边界模板

找最后一个小于等于 target 的位置，可以先找第一个大于 target 的位置，再减 1：

target

target

int upperBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left - 1;
}

int upperBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left - 1;
}

这种写法的好处是左右边界只记一套思路：找第一个满足条件的位置。

右边界容易写错，推荐转化成左边界问题：

最后一个小于等于 target 的位置 = 第一个大于 target 的位置 - 1。

target

target

最后一个小于 target 的位置 = 第一个大于等于 target 的位置 - 1。

target

target

这样不需要维护两套模板，面试手写时更稳。

答案二分

答案二分

答案二分不是在数组里找元素，而是在答案范围里找最小可行值或最大可行值。

典型问题：给定若干堆香蕉和总时间 h，求最小吃香蕉速度。速度越快，越容易在 h 小时内吃完，这就是单调性。

h

h

这类题通常分两步：

确定答案范围。比如速度最小是 1，最大不超过最大那堆香蕉数。

1

写 check 函数。给定一个速度，判断能不能在 h 小时内吃完。

check

h

这个上界成立依赖题目约束：h >= piles.length。因为速度等于最大堆大小时，每堆香蕉最多 1 小时吃完，总耗时不会超过堆数。

h >= piles.length

int minEatingSpeed(int[] piles, int h) {
    int left = 1;
    int right = 0;
    for (int pile : piles) {
        right = Math.max(right, pile);
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, h, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

boolean canFinish(int[] piles, int h, int speed) {
    long hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed;
    }
    return hours <= h;
}

int minEatingSpeed(int[] piles, int h) {
    int left = 1;
    int right = 0;
    for (int pile : piles) {
        right = Math.max(right, pile);
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, h, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

boolean canFinish(int[] piles, int h, int speed) {
    long hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed;
    }
    return hours <= h;
}

这里为什么返回 left？因为循环一直在找“第一个可行速度”。当 canFinish(mid) 为 true，说明 mid 可行，但可能还有更小的速度也可行，所以收缩右边界。最后左右边界重合的位置，就是最小可行速度。

left

canFinish(mid)

mid

答案二分的 check 函数往往比二分本身更重要。面试时建议先把 check 的含义说清楚，再写二分框架。

check

check

三类二分怎么选？

三类二分怎么选？

目标推荐模板返回值找到某个等于 target 的下标基础二分找到返回下标，找不到返回 -1找第一个满足条件的位置左边界返回 left，可能等于数组长度找最小可行答案答案二分返回最终的 left

目标推荐模板返回值

目标

推荐模板

返回值

找到某个等于 target 的下标基础二分找到返回下标，找不到返回 -1

找到某个等于 target 的下标

target

基础二分

找到返回下标，找不到返回 -1

-1

找第一个满足条件的位置左边界返回 left，可能等于数组长度

找第一个满足条件的位置

左边界

返回 left，可能等于数组长度

left

找最小可行答案答案二分返回最终的 left

找最小可行答案

答案二分

返回最终的 left

left

如果题目里有“第一个”“最后一个”“最小可行”“最大可行”，不要急着写基础二分，先判断是不是边界问题。

面试手写路径

面试手写路径

二分题的代码不长，面试里更容易被追问的是“你为什么敢丢掉一半”。手写时可以按这个顺序来：

先说明搜索空间：是在数组下标里找，还是在答案范围里找。

再说明单调性：mid 左右两侧为什么可以排除一边。

mid

明确区间含义：闭区间 [left, right] 还是左闭右开 [left, right)。

[left, right]

[left, right)

写更新规则：mid 还能不能成为答案，决定写 right = mid 还是 right = mid - 1。

mid

right = mid

right = mid - 1

最后说返回值：循环结束时 left、right 分别代表什么。

left

right

一个很实用的自检问题是：当 nums[mid] 正好满足条件时，我有没有把可能的答案删掉？ 左边界、答案二分里，mid 经常仍然可能是答案，所以不能随手写成 right = mid - 1。

nums[mid]

mid

right = mid - 1

代表题精讲：查找第一个和最后一个位置

代表题精讲：查找第一个和最后一个位置

1. 在排序数组中查找元素的第一个和最后一个位置 是边界二分的典型题。题目要求返回 target 的起始和结束位置，如果不存在返回 [-1, -1]。

34. 在排序数组中查找元素的第一个和最后一个位置

target

[-1, -1]

这题不要写成“找到一个 target 后向两边扫描”。虽然能过一些用例，但最坏情况下会退化成 O(n)。更稳的写法是做两次边界查找：

O(n)

第一次找第一个大于等于 target 的位置。

target

第二次找第一个大于 target 的位置，再减 1。

target

下面两个辅助方法与上文模板一致，这里保留完整代码，方便把返回值含义和主逻辑放在一起对照。

int[] searchRange(int[] nums, int target) {
    int left = lowerBound(nums, target);
    if (left == nums.length || nums[left] != target) {
        return new int[] {-1, -1};
    }
    int right = upperBound(nums, target) - 1;
    return new int[] {left, right};
}

int lowerBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int upperBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int[] searchRange(int[] nums, int target) {
    int left = lowerBound(nums, target);
    if (left == nums.length || nums[left] != target) {
        return new int[] {-1, -1};
    }
    int right = upperBound(nums, target) - 1;
    return new int[] {left, right};
}

int lowerBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int upperBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

面试里这题常见追问是：如果数组中全是 target 怎么办？如果 target 不存在但应该插在中间怎么办？这两个问题其实都在考返回值含义。lowerBound 返回的是第一个满足条件的位置，不保证这个位置上的值一定等于 target，所以返回前要再检查一次。

target

target

lowerBound

target

过程示意和边界样例

过程示意和边界样例

以左边界模板为例，数组 [1, 2, 2, 2, 4] 中找第一个大于等于 2 的位置：

[1, 2, 2, 2, 4]

2

轮次leftrightmid判断下一步1052nums[2] >= 2right = 22021nums[1] >= 2right = 13010nums[0] < 2left = 1结束11-left == right返回 1

轮次leftrightmid判断下一步

轮次

left

left

right

right

mid

mid

判断

下一步

1052nums[2] >= 2right = 2

1

0

5

2

nums[2] >= 2

nums[2] >= 2

right = 2

right = 2

2021nums[1] >= 2right = 1

2

0

2

1

nums[1] >= 2

nums[1] >= 2

right = 1

right = 1

3010nums[0] < 2left = 1

3

0

1

0

nums[0] < 2

nums[0] < 2

left = 1

left = 1

结束11-left == right返回 1

结束

1

1

-

left == right

left == right

返回 1

几个边界样例建议手写前先过一遍：

输入目标预期[]1返回 -1 或插入位置 0，看题目要求[1]1能命中唯一元素[1, 1, 1]左边界 1返回 0[1, 3, 5]左边界 4返回 2[1, 3, 5]左边界 6返回 3

输入目标预期

输入

目标

预期

[]1返回 -1 或插入位置 0，看题目要求

[]

[]

1

1

返回 -1 或插入位置 0，看题目要求

-1

0

[1]1能命中唯一元素

[1]

[1]

1

1

能命中唯一元素

[1, 1, 1]左边界 1返回 0

[1, 1, 1]

[1, 1, 1]

左边界 1

1

返回 0

0

[1, 3, 5]左边界 4返回 2

[1, 3, 5]

[1, 3, 5]

左边界 4

4

返回 2

2

[1, 3, 5]左边界 6返回 3

[1, 3, 5]

[1, 3, 5]

左边界 6

6

返回 3

3

常见错误写法：

while (left < right) {
    int mid = (left + right) / 2;
    if (nums[mid] >= target) {
        right = mid - 1; // 错：mid 可能就是左边界，不能直接排除
    } else {
        left = mid + 1;
    }
}

while (left < right) {
    int mid = (left + right) / 2;
    if (nums[mid] >= target) {
        right = mid - 1; // 错：mid 可能就是左边界，不能直接排除
    } else {
        left = mid + 1;
    }
}

左边界里，当 nums[mid] >= target 时，mid 仍然可能是答案，所以应该写 right = mid。

nums[mid] >= target

mid

right = mid

易错点

易错点

mid = (left + right) / 2 可能整数溢出，推荐写成 left + (right - left) / 2。

mid = (left + right) / 2

left + (right - left) / 2

不要混用闭区间和左闭右开区间的更新方式。

找边界时，命中目标后通常不能直接返回，还要继续收缩区间。

答案二分要先证明单调性，不能看到“最小值”就硬套。

canFinish 这类判断函数里可能需要 long，避免累计值溢出。

canFinish

long

高频问题自测

高频问题自测

left < right 和 left <= right 有什么区别？

left < right

left <= right

二分查找为什么是 O(logn)？

O(logn)

找左边界时，为什么命中后要移动 right？

right

什么是答案二分？它和普通二分有什么区别？

二分查找一定要求数组有序吗？

推荐练习题

推荐练习题

1. 二分查找

704. 二分查找

1. 搜索插入位置

35. 搜索插入位置

1. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

1. 爱吃香蕉的珂珂

875. 爱吃香蕉的珂珂

1. 在 D 天内送达包裹的能力

1011. 在 D 天内送达包裹的能力

写在最后

写在最后

如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。

GitHub

Gitee

JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。

如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。

知识星球