# 经典查找算法

## 二分法查找

![20210313090428873](/files/VBNHeRwVj9dcUb3sMovn)

二分搜索用于在一个单调或者局部单调有序数组中查找一个符合某些条件的值，时间复杂度为`O(logN)`。

1. 假设数量为N
2. 第一次查找位置为 `N / 2`，第二次查找为`N / 4`，后面依次为 `N / 8`...
3. 那么查找次数与N之间的关系为 `2 ^ x = N`
4. 所以，查找次数的时间复杂度的大O记法可表示为 `O(logN)`（以2为底）

**代码示例：**

1. 在一个有序数组中，找出某个数是否存在

   ```java
   /**
    * 在一个有序数组中，找出某个数是否存在
    */
   public boolean binarySearchExist(int[] sortedArray, int num) {
     if (sortedArray == null || sortedArray.length == 0) {
       return false;
     }
     int L = 0;
     int R = sortedArray.length - 1;
     int mid = 0;
     while (L < R) {
       // mid = (L + R) / 2;
       // 防止 L + R 所得的结果过大，溢出int类型最大值
       // 改造
       // mid = L + (R - L) / 2; // R 不会溢出，L 不会溢出， (R - L) / 2 更不会造成溢出
       // 等同于
       mid = L + ((R - L) >> 1);
       if (sortedArray[mid] == num) {
         return true;
       } else if (sortedArray[mid] > num) {
         R = mid;
       } else {
         L = mid;
       }
     }
     return sortedArray[mid] == num;
   }
   ```
2. 在一个有序数组中，找`>=`某个数最左侧的位置
3. 在一个有序数组中，找`<=`某个数最右侧的位置
4. 局部最小值问题

   ```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://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/jing-dian-cha-zhao-suan-fa.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.