# 二分搜索

## 簡介
二分搜索是經典使用 Divide and conquar 思想的算法，該算法的資料必須要事先排序好，才能做二分搜索。

## 二分搜索變化題解決思路

Leetcode 上的二分搜索變化題，通常是在基本的二分搜索上進行了一些變化和擴展，例如需要查找的數組不是一個傳統的排序數組，或者需要查找的元素不只是一個，甚至是一段區間。以下是一些二分搜索變化題的解法：

1. **在旋轉排序數組中查找目標值**：

首先使用二分法查找旋轉排序數組中的最小值，然後根據最小值將數組分為兩部分，再使用二分法分別在兩部分中查找目標值。

2. **搜索插入位置**：

直接使用二分法查找目標值，如果找到，返回該位置；如果沒找到，返回插入位置。

3. **在排序數組中查找元素的第一個和最後一個位置**：

分別使用二分法查找第一個和最後一個目標值的位置，需要注意邊界情況和查找失敗的情況。

4. **在旋轉排序數組中查找最小值**：

根據二分法的思想，每次比較中間位置的數字與左右兩端的數字，並根據比較結果縮小查找範圍。

5. **在有重複元素的排序數組中查找目標值**：

在二分法的基礎上，需要處理數組中有重複元素的情況。具體做法是，如果中間值等於目標值，繼續向左查找第一個等於目標值的位置，向右查找最後一個等於目標值的位置。

以上是幾個二分搜索變化題的解法，需要根據具體問題進行調整和優化，並進行適當的邊界處理和異常處理。

## 思路
upper 代表搜索範圍的**上邊界**
lower 代表搜索範圍的**下邊界**
1. 使用左閉右閉。
2. 每輪搜索先算出中間點，lower + (upper - lower) / 2 ，是為了防止數字溢出。
3. 開始比較
1. 如果 upper < lower，代表已經搜索完畢，沒有任何相符的值，返回 -1。
2. 如果 nums[mid] > target ，則代表 target 較小，下回合應該繼續比較左邊的數字 (lower, mid - 1)。
3. 如果 nums[mid] < target ，則代表 target 較大，下回合應該繼續比較右邊的數字 (mid + 1, upper)。
5. 最後因為 left <= right 所以 right 會在 left 左邊。

## 範例代碼

### 鎖定左右邊界

def binary_search_bound(bound: bool): # left bound: false, right bound: true
    left, right = 0, n - 1
    ans = -1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            ans = mid
            if bound:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
    return ans