建站
咨詢
售后
建站咨詢
新聞中心
目錄
創(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ù)；打造開(kāi)放共贏平臺(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)和眾多成功案例,為您定制開(kāi)發(fā)。1.?二分查找的概念
2.?整數(shù)的二分
2.1?二分的模版一
2.2?二分的模版二
2.3. 案例剖析
2.4.整數(shù)二分總結(jié)
3.?浮點(diǎn)數(shù)的二分
1.?二分查找的概念
2.?整數(shù)的二分折半查找(BinarySearch)技術(shù)，又稱為二分查找。它的前提是線性表中的記錄
必須是關(guān)鍵碼有序(通常從小到大有序)，線性表必須采用順序存儲(chǔ)。折半查找的基本思想是:在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵字相等，則查找成功; 若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找;若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過(guò)程，直
到查找成功，或所有查找區(qū)域無(wú)記錄，查找失敗為止。
二分的本質(zhì)：根據(jù)一定的條件或性質(zhì)(一般是與答案之間的關(guān)系)，可以將查找的區(qū)間分為兩部分，然后對(duì)中間值mid進(jìn)行判斷，確定答案在mid的左側(cè)還是右側(cè)，以此來(lái)縮小查找的范圍。
核心：保證答案在更新后的區(qū)間，當(dāng)區(qū)間長(zhǎng)度為1時(shí)我們就找到了答案。
二分查找是有兩個(gè)模版的，根據(jù)這兩個(gè)模版我們能夠解決幾乎全部的二分查找問(wèn)題。
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ù)答案來(lái)確定的，后面有例題可以幫助大家理解)，然后我們求出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?來(lái)算，那么 mid =?L +?L + 1 >>2 = L，我們發(fā)現(xiàn)?mid =?L，然后更新區(qū)間?L =?mid，即是?L =?L，區(qū)間并沒(méi)有變化，就會(huì)陷入死循環(huán)。由此，當(dāng)更新區(qū)間的方式為：L =?mid，R =?mid - 1 時(shí)計(jì)算 mid?的方式為：mid =?L +?R + 1 >>1。
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ù)組中的開(kāi)始位置和結(jié)束位置。
如果數(shù)組中不存在目標(biāo)值 target，返回?[-1, -1]。
你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問(wèn)題。
思路分析：
我們只需要進(jìn)行兩次二分查找，找到第一個(gè)target的下標(biāo)和最后一個(gè)target位置的下標(biāo)即可。
很據(jù)上面的基礎(chǔ)知識(shí)，來(lái)分析此題：
(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;
}
3.?浮點(diǎn)數(shù)的二分我們就是要根據(jù)一個(gè)條件(邊界)分出兩個(gè)區(qū)間來(lái)，本題也可以用其他條件，確定更新區(qū)間的方式。從而選擇使用哪個(gè)模板解決問(wèn)題。
核心：每次區(qū)間的更新都保證答案在新的區(qū)間中，當(dāng)區(qū)間長(zhǎng)度為1時(shí)，就能夠的到答案
注意：二分一定有解，然而具體的題目不一定有解。
因?yàn)楦↑c(diǎn)數(shù)不存在取整的問(wèn)題，所以比較簡(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)查看詳情吧
分享題目：二分查找----C/C++-創(chuàng)新互聯(lián)
文章來(lái)源：http://ef60e0e.cn/article/ceddig.html
