> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/00_binary_search/704.-binary-search.md).

# 704. Binary Search

<https://leetcode.com/problems/binary-search/>

## solution

* 左闭右闭

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1  # 闭区间

        while l <= r:  # 可能相等
            mid = l + (r - l) // 2
            if nums[mid] > target:
                r = mid - 1  # right - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid  # 输出mid
        return -1
```

时间复杂度：O(logn)\
空间复杂度：O(1)

* 左闭右开

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)  # 右开区间，需要右边界大于数组边界

        while l < r:  # 闭区间，则等于没有意义了
            mid = l + (r - l) // 2
            if nums[mid] > target:
                r = mid  # 闭区间，右边界本身就不在查找范围，因此mid不等于target也不在区间内
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid  # 输出mid
        return -1
```

* 左闭右开-lower bound

```python
class Solution:
    def lower_bound(self, nums, target):
        # find in range [left, right)
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:  # 即使相等, 右边也shrink
                right = mid
        return left  # 输出left
```

* 左闭右开-higher bound

```python
class Solution:
    def higher_bound(self, nums, target):
        # find in range [left, right)
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:  # 即使相等，左边也shrink
                left = mid + 1
            else:
                right = mid
        return left  # 输出left
```

## follow up

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

```python
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return l  # 相比704, 主要考察输出
```

[74. Search a 2D Matrix](https://github.com/LongxingTan/mle-interview/blob/main/01_leetcode/00_binary_search/74.%20Search%20a%202D%20Matrix.md)

[\*702. Search in a Sorted Array of Unknown Size](https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/)

```python
# 运用前提条件: [-9999, 9999]
```