# 二分搜

控制 index 真的他媽太難了==

## 比較不會錯的寫法

用一個變數 `start` 表示現在的位置，維護 loop invariant： `nums[start] < target`。

### 704. Binary Search

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 先特判 nums[0] 有沒有滿足 loop invariant
        if (nums[0] >= target){
            return (nums[0] == target)? 0 : -1;
        }
        int start = 0;
        int n = nums.size();
        // 跳跳跳
        // 一次跳半個總長
        for (int jmp = n/2; jmp > 0; jmp >>= 1){
            // 跳到腿斷掉為止
            while (jmp + start < n && nums[jmp + start] < target){
                start += jmp;
            }
        }
        // 現在 start 是最小的 index 滿足 start + 1 >= n 
        // 或 nums[start+1] >= target
        return (start + 1 < n && nums[start + 1] == target)? start + 1 : -1;
    }
};

## 這輩子再也不想寫的寫法
二分搜有幾個細節，一個是```while``` 裡面要小於還是小於等於，這就是爽就好，不管區間用左閉右開還是左閉右閉都可以，反正缺的條件最後 return 之前特判一下就好。

關鍵就是整個算法的 loop invariant 是什麼，白話文就是要維護包含答案的那個區間。

**維護最難的就是 `l` 跟 `r` 什麼時候要 assign 成 `m` 什麼時候要 assign 成 `m + 1`。**

不管是哪一種，重點就是**每次都要把 `mid` 從搜索區間排除**。下面用左閉右開解一題 leetcode，這有兩種寫法。

### 704. Binary Search
第一種是找到就壓右界，這種寫法維護的區間是：答案一定在含右端點的開區間（這還是開區間嗎）i.e., ``[l, r]`` 裡面。

class Solution {
public:
    int search(vector<int>& nums, int tar) {
        int l = 0, r = nums.size();
        while (l < r){
            int m = (l + r) / 2;
            if (tar <= nums[m]) r = m; //找到就壓右界，當然如果 tar 在左邊也是壓右界
            else l = m + 1; //找不到就升左界
        }
        return (r < nums.size() && nums[r] == tar)? r : -1;
        //如果最後右界是 nums.size() 那代表全部都找不到，因為如果有找到那右界一定會被壓過， i.e., r < nums.size()
    }
};

另一種是找到就升左界，這個維護的是：答案一定在`[l - 1, r]`裡面。

class Solution {
public:
    int search(vector<int>& nums, int tar) {
        int l = 0, r = nums.size();
        while (l < r){
            int m = (l + r) / 2;
            if (tar >= nums[m]) l = m + 1; //找到就升左界
            else r = m; //找不到就壓右界
        }
        return (l - 1 >= 0 && nums[l-1] == tar)? l-1 : -1;
        //如果最後左界 - 1 小於零那代表左界沒有被升過，i.e., 找不到
    }
};

以上兩種寫法就可以找到 `tar` 的左右邊界了，拿另一題示範一下。

### 34. Find First and Last Position of Element in Sorted Array

要找右邊界，就是找到 `tar` 的時候升左界；要找左邊界，就是找到 `tar` 的時候壓右界。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int tar) {
        // 先找左邊界，跟上面一樣
        int L, l = 0, r = nums.size();
        while (l < r){
            int m = (l + r) / 2;
            if (tar <= nums[m]) r = m;
            else l = m + 1;
        }
        // 找不到就 return
        if (r == nums.size() || nums[r] != tar) return vector<int>{-1,-1};
        else L = l;
        
        //再找右邊界
        l = 0, r = nums.size();
        while (l < r){
            int m = (l + r) / 2;
            if (tar >= nums[m]) l = m + 1;
            else r = m;
        }
        // 這邊 l - 1 一定是右邊界，因為找不到的情況已經在上面判掉了
        return vector<int>{L, l - 1};
        
    }
};