# Binary Search

**描述**：二分查找针对有序的数据集合，每次与区间中间元素对比，将待查找区间缩为一半，直到找到或区间被缩小为 0。

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-LyhB-C-EBVhZKHq8yyC%2F-LyhV6vf8CMLzNJnaTbt%2Fimage.png?alt=media\&token=a6b25383-d37e-46ec-b372-e8769f9b80b4)

**时间复杂度**：O(logn)，O(logn) 极其高效，**有时甚至比常量级更高效**。

**代码要点**：

* 循环退出条件：`low <= high`
* mid取值：`mid = (low + high) / 2`可能造成溢出，改为`low + ((high - low) >> 1)`
* `low = mid + 1, high = mid - 1`，而不是`low = mid, high = mid`，因为会造成死循环。

**局限性**：

* 依赖顺序表结构，因为需要下标**随机访问**。
* 需要**有序**数据。若不有序，需要插入、删除不频繁，一次排序多次查找的情况。
* 数据量小时没必要用二分，直接顺序查找。例外，数据比较耗时，如长度为300的字符串，那么此时就算数据量小也要二分。
* 数据量大不合适，因为需要连续内存。

{% hint style="info" %}
大部分情况，用二分查找解决的问题，都可以用散列表和二叉树解决，但是后者需要额外的内存空间。
{% endhint %}

二分查找**最简单**情况是有序数组中**不存在重复元素**，当有序数组中存在重复数据时，稍微复杂。二分查找变体：

**查找第一个值等于给定值的元素：**

```java
public static int search(int[] nums, int target) {
    if (nums == null) {
        return -1;
    }
    
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (nums[mid] > target) {
            high = mid - 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            if (mid == 0 || nums[mid - 1] < target) {
                return mid;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}
```

**查找最后一个值等于给定值得元素：**

**查找第一个大于等于给定值的元素：**

**查找最后一个小于等于给定值的元素：**

{% hint style="info" %}
对于等值查询，散列表和二叉树都能解决二分查找的问题，但是对于“近似”查询（如上面的四种变体），二分查找的优势就明显了。
{% endhint %}

## 例题

* [LeetCode 69：求平方根。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/search/LT69.java)


---

# 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://yunzhao.gitbook.io/notes/computer-science/algorithm/search.md?ask=<question>
```

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.