# Array Binary Search

## [Search for a Range](https://leetcode.com/problems/search-for-a-range/)

典型的 binary search 题，我还是比较喜欢用 left + 1 < right，不用担心各种奇葩输入导致的越界。

```java
public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftEnd = left, rightEnd = right;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target){
                right = mid;
            } else {
                left = mid;
            }
        }
        if(nums[left] == target) leftEnd = left;
        else if(nums[right] == target) leftEnd = right;
        else leftEnd = -1;

        left = 0;
        right = nums.length - 1;

        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target){
                left = mid;
            } else {
                right = mid;
            }
        }
        if(nums[right] == target) rightEnd = right;
        else if(nums[left] == target) rightEnd = left;
        else rightEnd = -1;

        int[] rst = new int[2];
        rst[0] = leftEnd;
        rst[1] = rightEnd;

        return rst;
    }
}
```

## [First Bad Version](https://leetcode.com/problems/first-bad-version/)

这道不是 LinkedIn 面经题。

是我被 DP 虐多了之后，来无耻地灌个水找找自信。。

```java
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid;
            } else {
                left = mid;
            }
        }

        if(isBadVersion(left)) return left;
        else if(isBadVersion(right)) return right;

        return -1;
    }
}
```

## [Search Insert Position](https://leetcode.com/problems/search-insert-position/)

这道不是 LinkedIn 面经题。

是我被 DP 虐多了之后，来无耻地灌个水找找自信。。

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

        if(target <= nums[left]) return left;
        if(target <= nums[right]) return right;
        if(target > nums[right]) return right + 1;

        return 0;
    }
}
```

## [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)

这题在地里看到过，当时把猴子给弄挂了。。

### 这题很重要的性质是，没有重复元素。

![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2Fefa4404e163496d55c6a278f62ba161b451dcbe2.jpg?generation=1614792531721952\&alt=media)

### 可以根据 A\[mid] 与 A\[right] 的大小关系，先行判断 mid 一定位于哪一端；

### 对于已经确定 mid 左/右  的数组，必然有一段区间满足单调性，可以利用来做 binary search.

```java
public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left + 1 < right){
            int mid = left + (right - left) / 2;

            if(nums[mid] >= nums[right]){
                if(target <= nums[mid] && target >= nums[left]){
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                if(target >= nums[mid] && target <= nums[right]){
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }

        if(nums[left] == target) return left;
        if(nums[right] == target) return right;

        return -1;
    }
}
```

## [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

在把上一道题做完之后，这题就是一个乞丐版的 search in rotated sorted array. 因为已知没有 duplicates 就更简单了。

```java
public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[right]){
                left = mid;
            } else {
                right = mid;
            }
        }

        return Math.min(nums[left], nums[right]);
    }
}
```

## [Find Minimum in Rotated Sorted Array II](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

加上有重复元素的条件之后，这题立刻就变成 Hard 难度了。原因在于出现了新情况，即我们不知道最小值到底在 mid 的左边还是右边，比如【3,\[3],1,3】，中间的 3 和两端值都相等，无法正确地直接砍掉一半。

* **我们依然可以靠 A\[mid] 与 A\[right] 的大小关系来二分搜索；**
  * **A\[mid] > A\[right] 时，mid 在左半边，最小值一定在 mid 右侧；**
  * **A\[mid] < A\[right] 时，mid 在右半边，最小值一定在 mid 左侧；**
* **A\[mid] == A\[right] 时，无法判断，把 right 向左挪一格。**

```java
public class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[right]){
                left = mid;
            } else if(nums[mid] < nums[right]){
                right = mid;
            } else {
                right --;
            }
        }

        return Math.min(nums[left], nums[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://mnunknown.gitbook.io/algorithm-notes/binary_search_lei/array_binary_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.