這篇文章解決若幹問題：
如果遞增序列A中的元素可能重複，那麼如何對給定想查找的元素x：
- 求出序列中第一個大于等于x的元素的位置；
- 求出序列中第一個大于x的元素的位置；
- 求出序列中第一個滿足某條件的位置；
- 求出序列中最後一個小于等于x的元素的位置；
- 求出序列中最後一個小于x的元素的位置。
第一個大于等于x和第一個大于x的元素的位置
舉個栗子：對數組序列{1,3,3,3,6}（下标從0開始）來說，若查詢3，則得到L=1、R=4。
如果查詢8，則得到L=R=5。
如果序列中沒有x，那麼L和R也可以了解為假設序列中存在x，則x應當在的位置。
現在，來解決第一個小問吧。
如果已經對二分查找能單獨根據腦子裡的想的寫出代碼的時候，lower_bound和upper_bound也能寫出來。下面給出代碼，讀者可以嘗試畫個數組後按代碼中算法推導出來。
其中注意：
對于lower_bound
第一
循環條件為
，而不是二分查找的left<right
。在二手查找的問題中，需要元素不存在時傳回-1，這樣當left<=right
時left>right
[left,right]
就不再是閉區間（失去比較的意義），是以可以作為元素不存在的判定規則。
但是如果想要傳回第一個大于等于x的元素的位置，就需要判斷元素x本身是否存在（就算不存在，傳回的也是“若存在應該在的位置”），于是乎當
left<right
時讓循環一直執行即可。
第二
由于
left==right
時while循環終止，是以最後的傳回值既可以是left，也可以是right。
最後
二分的初始區間的原則是應當能覆寫到所有可能傳回的結果。
二分下界0可以确定，但是上界是n還是n-1？考慮到想要查詢元素x有可能比序列中所有元素都要大，此時應該傳回n（若n在數列中存在則它應該在的位置）。是以上界為n。
二分的初始區間為
。[left,right]=[0,n]
代碼如下:
//left=0 right=n(注意不是n-1)
int lower_bound(int A[],int left,int right,int x){ //對于元素x，就算不存在于A中，也可以傳回所需要的值
int mid;
while(left<right){ //left==right意味着找到了唯一的位置
mid=(left+right)/2;
if(A[mid]>=x){
right=mid;
}
else{
left=mid+1;
}
}
return left; //傳回查找的位置(當left==right時，循環停止，是以此時left=right)
}
int upper_bound(int A[],int left,int right,int x){
int mid;
while(left<right){
mid=(left+right)/2;
if(A[mid]>x){
right=mid;
}
else{
left=mid+1;
}
}
return left;//傳回查找的位置(此時left>right，left即為第一個大于x的元素的位置)
} 複制
第一個滿足某條件 C 的位置
尋找有序序列中第一個滿足某條件 C 的元素的位置
代碼如下：
//二分區間為左閉右閉的[left, right]，初值必須能覆寫解的所有可能取值
int solve(int left, int right)
{
int mid;
while(left < right)//對于[left,right],兩者相同即找到唯一位置
{
mid = left + right / 2;
if (條件成立) //條件成立，第一個滿足條件的元素的位置 <=mid
{
right = mid; //往左子區間[left, mid]找
}
else //條件不成立，第一個滿足該條件的位置>mid
{
left = mid + 1; //往右子區間[mid+1, right]找
}
}
return left; //最後傳回夾出來的位置
} 複制
舉個栗子：
想要求第一個滿足大于等于10的元素，則可以這樣寫。
代碼如下：
#include<stdio.h>
//二分區間為左閉右閉的[left, right]，初值必須能覆寫解的所有可能取值
const int n = 10;
int solve(int A[], int left, int right)
{
int mid;
while(left < right)//對于[left,right],兩者相同即找到唯一位置
{
mid = (left + right) / 2;
if (A[mid] >= 10) //條件成立，第一個滿足條件的元素的位置 <=mid
{
right = mid; //往左子區間[left, mid]找
}
else //條件不成立，第一個滿足該條件的位置>mid
{
left = mid + 1; //往右子區間[mid+1, right]找
}
}
return left; //最後傳回夾出來的位置
}
int main(){
int a[n] = {2,5,8,11,13,14,18,20,22,25};
printf("%d\n",solve(a,0,n));
return 0;
} 複制
如果尋找最後一個滿足“條件C”的元素的位置，則可以先求第一個滿足“條件!C”的元素的位置。（比如，最長回文子串就用到了這一點）
先挖個坑，以後回來補
模闆拓展（區間左開右閉）
實際上這種左開右閉區間的寫法與左閉右閉區間的寫法是等價的。
在這種寫法下，循環條件變成了left + 1 < right，并且當left+1==right退出循環，使得(left,right]是唯一位置。
由于從左閉變成了左開，是以left的初值要比解的最小值小1（例如對下标為0序列，left的初值為-1，而right的初值不變，還是n），同時，left=mid+1應該改成left=mid（這裡想想為什麼？挖坑，待解決），并且，傳回的值應該是right，而不是left。
//二分區間為左閉右閉的(left, right]，初值必須能覆寫解的所有可能取值 int solve(int left, int right) { int mid; while(left + 1 < right) { mid = (left + right) / 2; if (條件成立) //條件成立，第一個滿足條件的元素的位置 <=mid { right = mid; } else //條件不成立，第一個滿足該條件的位置>mid { left = mid; } } return right; }
舉個栗子：
同樣求第一個大于等于10的元素。
代碼如下：
#include<stdio.h> //二分區間為左開右閉的(left, right]，初值必須能覆寫解的所有可能取值 const int n = 10; int solve(int A[], int left, int right) { int mid; while(left + 1 < right)//對于[left+1,right],兩者相同即找到唯一位置 { mid = (left + right) / 2; if (A[mid] >= 10) //條件成立，第一個滿足條件的元素的位置 <=mid { right = mid; //往左子區間[left, mid]找 } else //條件不成立，第一個滿足該條件的位置>mid { left = mid; //往右子區間[mid, right]找 } } return right; //最後傳回夾出來的位置 } int main(){ int a[n] = {2,5,8,11,13,14,18,20,22,25}; printf("%d\n",solve(a,-1,n)); return 0; }
輸出：3
值得注意的是，如果solve函數中傳回的是left，則輸出2。
最後一個小于等于x和最後一個小于x的元素的位置
既然我們現在已經能求出序列中第一個大于等于x的元素的位置和第一個大于x的元素的位置這種問題了。
那怎麼求出最後一個小于等于x的位置和求出最後一個小于x的位置？
隻要按照lower_bound和upper_bound的算法自己進行推算，就能出答案了，下面是部落客自己根據上面推算的代碼。如果有錯誤，請指正。
代碼：
#include <iostream>
using namespace std;
int lower_bound(int A[], int left, int right, int x){
int mid;
while(left <= right){
mid = (left + right) / 2;
if(A[mid] <= x)
left = mid + 1;
else
right = mid -1;
}
return right;
}
int upper_bound(int A[], int left, int right, int x){
int mid;
while(left <= right){
mid = (left + right) / 2;
if(A[mid] < x)
left = mid + 1;
else
right = mid -1;
}
return right;
}
int main(){
int n, x;
cin>>n;
cin>>x;
int a[n];
for(int i = 0; i < n; i++)
{
cin>>a[i];
}
cout << lower_bound(a, 0, n-1, x) <<" "<< upper_bound(a, 0, n-1, x);
return 0;
} 複制
這裡提供另外一種參數僅供參考:
int lower_bound(int a[], int n, int x){
int left = 0 , right = n - 1, mid;
......
}
int upper_bound(int a[], int n, int x){
int left = 0 , right = n - 1, mid;
......
}
int main(){
......
cout << lower_bound(a, n, x) <<" "<< upper_bound(a, n, x);
......
} 複制
參考
3.9-2求解查找最後一個小于等于指定元素的問題
二分算法(詳細分類版)
版權所有：可定部落格 © WNAG.COM.CN
本文标題：《二分查找的延伸》
本文連結：https://wnag.com.cn/833.html
特别聲明：除特别标注，本站文章均為原創，本站文章原則上禁止轉載，如确實要轉載，請電聯：[email protected]，尊重他人勞動成果，謝過~