# Binary Search
标准二分查找
```java
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while (left <= right) { // 注意
int mid = (right + left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // 注意
} else if (nums[mid] > target) {
right = mid - 1; // 注意
}
}
return -1;
}
```
**为什么 while 循环的条件中是 <=，而不是 <** 答：因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。
这二者可能出现在不同功能的二分查找中，区别是：**前者相当于两端都闭区间 \[left, right]，后者相当于左闭右开区间 \[left, right)**，因为索引大小为 nums.length 是越界的。
我们这个算法中使用的是 **\[left, right] 两端都闭的区间。这个区间就是每次进行搜索的区间，我们不妨称为「搜索区间」**(search space)。
什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：
```java
if (nums[mid] == target)
return mid;
```
但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？**搜索区间为空的时候应该终止**，意味着你没得找了，就等于没找到嘛。
**while(left <= right)的终止条件是 left == right + 1，写成区间的形式就是 \[right + 1, right]，或者带个具体的数字进去 \[3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。**
**while(left < right)的终止条件是 left == right，写成区间的形式就是 \[right, right]，或者带个具体的数字进去 \[2, 2]，这时候搜索区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 \[2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就可能出现错误。**
当然，如果你非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：
```java
//...
while(left < right) {
// ...
}
return nums[left] == target ? left : -1;
```
为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？
答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。
刚才明确了「搜索区间」这个概念，**而且本算法的搜索区间是两端都闭的，即 \[left, right]。那么当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？**
**当然是去搜索 \[left, mid - 1] 或者 \[mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。**
此算法有什么缺陷？
答：至此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。
比如说给你有序数组 nums = \[1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
这样的需求很常见。你也许会说，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的时间复杂度了。
第一个，最基本的二分查找算法：
```
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
```
第二个，寻找左侧边界的二分查找：
```
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界 right = mid - 1;
```
第三个，寻找右侧边界的二分查找：
```
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界 left = mid + 1;
又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://wentao-shao.gitbook.io/leetcode/binary-search.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.