二分查找----C/C++-創(chuàng)新互聯(lián)

目錄

創(chuàng)新互聯(lián)長(zhǎng)期為上1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為寧陵企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作，寧陵網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

1.?二分查找的概念

2.?整數(shù)的二分

2.1?二分的模版一

2.2?二分的模版二

2.3. 案例剖析

2.4.整數(shù)二分總結(jié)

3.?浮點(diǎn)數(shù)的二分

1.?二分查找的概念

折半查找(BinarySearch)技術(shù)，又稱為二分查找。它的前提是線性表中的記錄
必須是關(guān)鍵碼有序(通常從小到大有序)，線性表必須采用順序存儲(chǔ)。

折半查找的基本思想是:在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵字相等，則查找成功; 若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找;若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直
到查找成功，或所有查找區(qū)域無記錄，查找失敗為止。

2.?整數(shù)的二分

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

核心：保證答案在更新后的區(qū)間，當(dāng)區(qū)間長(zhǎng)度為1時(shí)我們就找到了答案。

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

2.1?二分的模版一
int main()
{
	int L = 0;
	int R = length - 1; //length為數(shù)組的長(zhǎng)度

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

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

為什么mid =?L + R + 1 >>1???，這是由我們更新區(qū)間的方式?jīng)Q定了的，我們假設(shè)?L =?R - 1時(shí)，如果按照?mid = L + R >>1?來算，那么 mid =?L +?L + 1 >>2 = L，我們發(fā)現(xiàn)?mid =?L，然后更新區(qū)間?L =?mid，即是?L =?L，區(qū)間并沒有變化，就會(huì)陷入死循環(huán)。由此，當(dāng)更新區(qū)間的方式為：L =?mid，R =?mid - 1 時(shí)計(jì)算 mid?的方式為：mid =?L +?R + 1 >>1。

2.2?二分的模版二
int main()
{
	int L = 0;
	int R = length - 1; //length為數(shù)組的長(zhǎng)度

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

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

2.3. 案例剖析

原題鏈接：

34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置 - 力扣（LeetCode）https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

題目描述：

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回?[-1, -1]。

你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問題。

思路分析：

我們只需要進(jìn)行兩次二分查找，找到第一個(gè)target的下標(biāo)和最后一個(gè)target位置的下標(biāo)即可。

很據(jù)上面的基礎(chǔ)知識(shí)，來分析此題：

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

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

循環(huán)結(jié)束時(shí) L =?R?的最后返回?L?或則?R?都行，前提是 target 存在哈。

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    //放結(jié)果的數(shù)組
    int* array = (int*)malloc(sizeof(int) * 2);
    //返回的數(shù)組大小都是2
    *returnSize = 2;
    //如果是空的數(shù)組，返回兩個(gè)-1
    if(numsSize == 0)
    {
        array[0] = -1;
        array[1] = -1;
        return array;
    }
    //找第一個(gè)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，返回兩個(gè)-1
    if(nums[L] != target)
    {
        array[0] = -1;
        array[1] = -1;
        return array;
    }
    //保存結(jié)果
    array[0] = L;
    //找第二個(gè)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;
    }
    //保存結(jié)果
    array[1] = L;
    return array;
}

2.4.整數(shù)二分總結(jié)

我們就是要根據(jù)一個(gè)條件(邊界)分出兩個(gè)區(qū)間來，本題也可以用其他條件，確定更新區(qū)間的方式。從而選擇使用哪個(gè)模板解決問題。

核心：每次區(qū)間的更新都保證答案在新的區(qū)間中，當(dāng)區(qū)間長(zhǎng)度為1時(shí)，就能夠的到答案

注意：二分一定有解，然而具體的題目不一定有解。

3.?浮點(diǎn)數(shù)的二分

因?yàn)楦↑c(diǎn)數(shù)不存在取整的問題，所以比較簡(jiǎn)單。

那個(gè) cin >>x?就是?scanf("%d", &x);

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：二分查找----C/C++-創(chuàng)新互聯(lián)
鏈接URL：http://bm7419.com/article6/ceddig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、App設(shè)計(jì)、網(wǎng)站導(dǎo)航、品牌網(wǎng)站制作、Google、營(yíng)銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都做網(wǎng)站