二分，相信對于大多數初涉演算法的同學來說，真的是玄學編程，主體思想容易至極，可是細節處理，邊界處理，真的是無比難受，本文結合筆者踩過的坑，意圖帶大家搞清二分的本質，
二分法通常有四種常見型別，我們逐一來看，若想速查，可直接看最后總結，
說明: int mid = left + (right-left) / 2; 等價于 int mid = (left + right) / 2; 只是后者在演算法比賽中 left + right 可能會超出整形范圍導致結果出錯，建議使用前一種形式，后文不在解釋，

一.尋找唯一值

這種二分是整數二分中最基本的一種，我們以力扣35. 搜索插入位置為例進行講解，
題目為:

二分的前提是必須是有序陣列，本質思想為取中進行條件判斷，每次根據判定結果將搜索區間減少一半，最終確定目標值，
下面附上代碼，請讀者一定要注意標明的坑點:

int searchInsert(int* nums, int numsSize, int target)
{
    int left = 0;
    int right = numsSize - 1;	//坑點1
    while (left <= right) {		//坑點2
        int mid = left + (right-left) / 2;
        if (nums[mid] == target) {
            return mid;		//找到該數，回傳
        }
        //坑點3
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    //未找到時根據題目要求進行處理，這部分要根據題意，就不帶大家分析了~
    if (left >= numsSize) {
        return numsSize;
    }
    return nums[left]<target ? right : left;
}

1.右邊界定義

這種情況下，要求我們搜素一個數字，我們定義二分右邊界為陣列末尾元素下標（陣列長度-1），如此我們的搜索區間為 [left, right]，右邊為閉區間，這種情況下，如此定義是比較簡單的，

2.回圈終止條件

看回圈終止條件首先就得看我們的搜索區間 [left,right]，為閉區間，也就是說，當 left == right 時我們的搜索區間里還有一個數left或者right未經判斷，所以這時還得進入回圈，判斷這個數是不是滿足條件，
當然，我們知道原因后，也可以寫成 <不過回圈退出后，我們要對left或者right這個數特殊判斷一下，下文統一使用 left:

while (left < right) {
	.....
}
if (nums[left] == target) {
	return left;
}
// 未找到，根據題目要求處理，

3.條件更新

這里就很迷惑了，很多時候我們可以看到 left = mid, left = mid + 1, right = mid, right = mid + 1,到底該如何選擇？
針對這種情況，我們思考，當我們要進行條件更新意味著什么？意味著我們現在的 mid 并不滿足條件，而我們的搜索區間為閉區間，所以我們要將 mid 在接下來的搜索中排除，即將搜索區間更新為 [left, mid-1] 或者 [mid+1, right]，這樣我們的條件更新自然就是：

left = mid + 1;
right = mid - 1;

二.尋找左邊界

這種情況是上一種二分的進階，要求是在一排序好的陣列里，查找滿足某一性質的值的最小下標，我們仍以力扣 34. 在排序陣列中查找元素的第一個和最后一個位置進行決議，（這題使用C++ vector容器，本質就是陣列）
題目如下：

這道題目要求查找左右邊界，我們先看左邊界查找，還是一樣，注意坑點：

    int LeftSearch(vector<int>& nums, int target)
    {
        int left = 0;
        int right = nums.size();	//坑點1
        while (left < right) {		//坑點2
            int mid = left + (right-left) / 2;
            //坑點3
            if (nums[mid] >= target) {
                right = mid;
            }
            else {   // nums[mid] < target
                left = mid + 1;
            }
        }
        //未找到處理，坑點4!
        if (left == nums.size()) {
            return -1;
        }
        return nums[left]==target ? left : -1;
    }

1.右邊界定義

這里要求我們搜素一個范圍的左邊界，我們定義右邊界為陣列長度（陣列末尾元素下標+1），這就意味著我們的搜索區間為 [left, right) 為左閉右開區間，

2.回圈終止條件判斷

同樣的，看回圈終止條件就得看搜索區間，我們的搜索區間為 [left, right) 左閉右開，當 left == right 時，[left, left) 區間已經是空區間，無需再次進入回圈進行判斷，

3.條件更新

這里也是最難理解的一點，
首先，我們得想兩個問題：

①回圈終止條件？

答：當 left == right 回圈退出，

②如果存在答案，答案保存在哪里？(重要)

這里，我們得理解，像第一種情況，找一個確定的數字，我們只要找到了就可以直接break退出回圈，但下面這兩種情況，我們如果找到了一個滿足條件的數，是不能直接退出回圈的，因為我們要找的是這組數的邊界！所以我們只能退出回圈時，將我們的答案卡在區間里，所以，回圈結束后，left 或right就是我們的答案！

所以，當 nums[mid] >= target 時，我們的 mid 肯定是左邊界，或者左邊界的右側，這時，我們只能令 right = mid，如果令 right = mid - 1，當mid就是左邊界時，我們就完美的避開了答案，
同理，當 nums[mid] < target 時，mid 一定在左邊界的左側，此時，我們就要讓 left = mid + 1，查找mid 的右側區域，
這里，請不要疑惑，為什么將等號放在 nums[mid] >= target 而不放在 <= 那里，因為我們查找左邊界，本質上可以理解為，查找一排序陣列中大于等于target的最小下標，而你不能理解為，小于等于target的最大下標，因為那樣找出來的是右邊界！

4.額外判斷

一句話：我們查找左邊界，本質上可以理解為，查找一排序陣列中大于等于target的最小下標，所以，嚴格來說，我們找到的那個值的大于等于target的，所以我們得判斷，這個值是不是target，若不是，說明陣列中壓根不存在target，我們回傳-1，
還有一種情況是 target 大于陣列最后一個元素，這種情況下 left 會一直更新到 right 的位置，造成越界，我們得特殊判斷一下，

三.尋找右邊界

右邊界查找與左邊界比較相似，還是上題，我們附上代碼：

    int RightSearch(vector<int>& nums, int target)
    {
        int left = 0;
        int right = nums.size(); //坑點1
        while (left < right) {   //坑點2
            int mid = left + (right - left) / 2;
            //坑點3
            if (nums[mid] <= target) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        //坑點4
        if (left - 1 >= nums.size() || left - 1 < 0) {
            return -1;
        }
        if (nums[left-1] != target) {
            return -1;
        }
        return left - 1;
    }

1. 右邊界定義 & 回圈條件判斷

這里我們的要求依舊是找一組數的邊界，所以我們仍然將右邊界定義為陣列長度，回圈條件為 left < right，與左邊界處理情況相同，

2. 條件更新

尋找右邊界，可以理解為查找小于等于target的最大下標，
那么，按照左邊界的理解，我們似乎應該將條件更新寫成這樣：

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

這樣寫似乎順理成章，nums[mid] <= target 時，右邊界在mid或mid的右側，所以我們令 left = mid，反之，right = mid - 1，可是，如果這樣寫，會有一個致命的問題：
看這樣一個測驗用例：

nums[] = {1};
target = 1;

初始化，left = 0， right = nums.size() = 1; 進入回圈，mid = (left + right) / 2 = 1 / 2 = 0;
nums[mid] <= target, left = mid = 0; 這里問題就出現了，一次回圈過后 left 和 right 都沒有得到更新，所以就會造成死回圈!
故我們可以得出結論：由于整除的特殊性質，為避免死回圈情況的出現，我們進行整數二分條件更新時，一定不能直接寫 left = mid ！！
所以，我們只能寫成這樣：

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

4. 額外判斷

請思考一個問題，這種情況下，我們跳出回圈后，如果存在答案，保存在哪里？

     if (nums[mid] <= target) {
         left = mid + 1;
     }

我們思考，當此時的 mid 就是我們尋找的右邊界時，我們令 left = mid + 1，也就是說，這種情況下，我們的右邊界保存在 left - 1 里!!
如此，我們的判斷部分就很好理解了，首先，我們判斷 left - 1 這個下標是否合法:

        if (left - 1 >= nums.size() || left - 1 < 0) {
            return -1;
        }

然后判斷 nums[left-1] 這個數是不是我們要找的 target：

        if (nums[left-1] != target) {
            return -1;
        }

如果都沒問題，就可以回傳 left - 1 了，

附：如果實在不理解為什么要加這么多判斷，可以把它們選擇性省略，然后到力扣提交，就可以看到對應的測驗用例了~

四.浮點數二分

浮點數二分可謂是最為簡單的二分型別，幾乎都不要考慮邊界條件，我們直接以AcWing上的一道模板題為例: 790.數的三次方根
題目如下：

寫浮點數二分，最主要的是注意它的資料范圍，附上代碼：

#include <iostream>

using namespace std;

int main()
{
	double x;
	cin >> x;

	double left = -10000;
	double right = 10000;

	while (right - left > 1e-8) {
		double mid = (left + right) / 2;
		if (mid*mid*mid > x)
			right = mid;
		else
			left = mid;
	}
	printf("%.6lf", left);
	
	return 0;
}

我們可以直接以題目所給的資料范圍作為左右邊界，這樣便無需考慮一些特殊情況（如0-1的數開方比原數大），
浮點數二分我們需要定義一個精度，一般定義的精度比題目要求的精度多兩個小數點最為保險，
當 left 和 right 之間的距離小于這個精度時，我們就認為這個區間里任意一個數都可以作為答案，此時跳出回圈，直接輸出 left 就好了，
注：新手在寫的時候要注意，浮點二分所有的資料型別都是 double 可不要一個手滑寫成 int，完了出錯還傻傻的半天還找不出來，(嗚嗚嗚~)

五. 整數二分總結

浮點數二分較為簡單，我們總結一下整數二分，

特別注意，尋找右邊界時，回傳的答案是保存在 left - 1 里的!!