> 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]
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://longxingtan.gitbook.io/mle-interview/01_leetcode/00_binary_search/704.-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.