二分查找----C/C++-創新互聯

創新互聯長期為上1000家客戶提供的網站建設服務，團隊從業經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯網生態環境。為寧陵企業提供專業的成都網站設計、網站制作，寧陵網站改版等技術服務。擁有10余年豐富建站經驗和眾多成功案例,為您定制開發。

1.?二分查找的概念

2.?整數的二分

2.1?二分的模版一

2.2?二分的模版二

2.3. 案例剖析

2.4.整數二分總結

3.?浮點數的二分

1.?二分查找的概念

折半查找(BinarySearch)技術，又稱為二分查找。它的前提是線性表中的記錄
必須是關鍵碼有序(通常從小到大有序)，線性表必須采用順序存儲。
折半查找的基本思想是:在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功; 若給定值小于中間記錄的關鍵字，則在中間記錄的左半區繼續查找;若給定值大于中間記錄的關鍵字，則在中間記錄的右半區繼續查找。不斷重復上述過程，直
到查找成功，或所有查找區域無記錄，查找失敗為止。

2.?整數的二分

二分的本質：根據一定的條件或性質(一般是與答案之間的關系)，可以將查找的區間分為兩部分，然后對中間值mid進行判斷，確定答案在mid的左側還是右側，以此來縮小查找的范圍。

核心：保證答案在更新后的區間，當區間長度為1時我們就找到了答案。

二分查找是有兩個模版的，根據這兩個模版我們能夠解決幾乎全部的二分查找問題。

2.1?二分的模版一

int main()
{
	int L = 0;
	int R = length - 1; //length為數組的長度

	while (L< R)
	{
		int mid = L + R + 1 >>1;
		if (check(mid)) //檢查mid指向的元素在答案所分的兩個區間的哪一側
			L = mid;
		else
			R = mid - 1;
	}
	return 0;
}

上圖中，假設我們要確定的是綠色的點，在綠色區間的元素滿足一定的條件，紅色區間的元素也滿足一定的條件(這兩個區間的條件就是根據答案來確定的，后面有例題可以幫助大家理解)，然后我們求出mid所在的區間，假設mid滿足綠色區間的條件，那么答案（要確定的綠色的點）肯定在mid的右側，并且mid也可能是答案，所以答案在 [ mid, R?],? 更新方式為：?L = mid；當mid不滿足綠色區間的性質，那么mid就滿足紅色區間的性質，此時mid不可能是答案（要確定的綠色的點），所以答案就在 [ L, mid - 1 ]?的區間內，更新區間的方式：R =?mid - 1。

為什么mid =?L + R + 1 >>1???，這是由我們更新區間的方式決定了的，我們假設?L =?R - 1時，如果按照?mid = L + R >>1?來算，那么 mid =?L +?L + 1 >>2 = L，我們發現?mid =?L，然后更新區間?L =?mid，即是?L =?L，區間并沒有變化，就會陷入死循環。由此，當更新區間的方式為：L =?mid，R =?mid - 1 時計算 mid?的方式為：mid =?L +?R + 1 >>1。

2.2?二分的模版二

int main()
{
	int L = 0;
	int R = length - 1; //length為數組的長度

	while (L< R)
	{
		int mid = L + R >>1;
		if (check(mid)) //檢查mid指向的元素在答案所分的兩個區間的哪一側
			L = mid + 1;
		else
			R = mid;
	}
	return 0;
}

上圖中，假設我們要確定的是紅色的邊界點，我們求出mid，檢查mid是否滿足紅色區間的條件，如果滿足，則mid在紅色區間，并且mid可能是答案，所以答案(要確定的紅色點的下標)?在 [L, mid ]區間內，更新方式?R =?mid，同理當mid不滿足紅色區間的條件，答案就在 [ mid + 1, R?]?的區間內，更新區間的方式為：L =?mid + 1。

2.3. 案例剖析

原題鏈接：
34. 在排序數組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

題目描述：
給你一個按照非遞減順序排列的整數數組 nums，和一個目標值 target。請你找出給定目標值在數組中的開始位置和結束位置。
如果數組中不存在目標值 target，返回?[-1, -1]。
你必須設計并實現時間復雜度為?O(log n)?的算法解決此問題。

思路分析：

我們只需要進行兩次二分查找，找到第一個target的下標和最后一個target位置的下標即可。

很據上面的基礎知識，來分析此題：

(1)：找第一個?target 的下標。非遞減序列，第一個 target?將整個序列分為兩部分，后面區間的元素滿足 >=?target?的條件，如果 mid?滿足 >= target?的條件那么mid?就在后面的區間，并且mid可能是第一個target(條件是 >= target嘛)，所以答案就在 [ L,?mid?]，更新方式為?R =?mid，一旦我們確定了更新方式就知道了該用哪一個模板，顯然就是模板二。然后就只需要套模板就行。

(2)：找最后一個 target 的下標。非遞減序列，最后一個 target?將整個序列分為兩部分，前面區間的元素滿足<=?target?的條件，如果 mid?滿足<= target?的條件那么mid?就在前面的區間，并且mid可能是最后一個target(條件是<= target嘛)，所以答案就在 [?mid, R?]，更新方式為 L?=?mid，一旦我們確定了更新方式就知道了該用哪一個模板，顯然就是模板一。然后就只需要套模板就行。

循環結束時 L =?R?的最后返回?L?或則?R?都行，前提是 target 存在哈。

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    //放結果的數組
    int* array = (int*)malloc(sizeof(int) * 2);
    //返回的數組大小都是2
    *returnSize = 2;
    //如果是空的數組，返回兩個-1
    if(numsSize == 0)
    {
        array[0] = -1;
        array[1] = -1;
        return array;
    }
    //找第一個target
    int L = 0, R = numsSize - 1;
    while(L< R)
    {
        //模板二
        int mid = L + R >>1;
        if(nums[mid] >= target)
            R = mid;
        else
            L = mid + 1;
    }
    //如果找不到target，返回兩個-1
    if(nums[L] != target)
    {
        array[0] = -1;
        array[1] = -1;
        return array;
    }
    //保存結果
    array[0] = L;
    //找第二個target
    L = 0;
    R = numsSize - 1;
    while(L< R)
    {
        //模版一
        int mid = L + R + 1 >>1;
        if(nums[mid]<= target)
            L = mid;
        else
            R = mid - 1;
    }
    //保存結果
    array[1] = L;
    return array;
}