簡單的二分查找
很容易理解，但是二分查找的前提是序列是有序的，每次都是通過跟區間的中間元素對比，將待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間被縮小為0，
二分查找只能用在資料是通過順序表結構存盤的資料結構上，如陣列，如果是其他的結構存盤則不適合用二分查找，如鏈表，
二分查找的時間復雜度為O(logn).
簡答二分查找的代碼如下：
int binarySearch(int A[], int n, int x){
//left 和right為陣列的左右區間下標
int left = 0, right =n-1, mid;
while(left <= right){
mid = left + ( right - left) / 2; //當陣列數量較多時為了防止left+right超過int范圍，
if(A[mid] == x) return mid; //找到x，回傳下標
else if(A[mid] > x){
right = mid-1;
} else{
left = mid+1;
}
}
return -1; //沒有找到，回傳-1，
}
二分查找變體：
如果序列A中的元素可能重復，所以查找時會出現以下變體型別的二分查找，該思想是在學習極客時間的王錚資料結構與演算法時學習的，對我來說比很多書上寫得更加容易理解和記憶，
查找序列中第一個等于x的元素的位置
因為陣列中有重復值，找到的x不一定是第一個出現的，所以可以在上面簡單二分查找的基礎上判斷當A[mid]=x 時，判斷是不是第一個，如果此時mid=0或者A[mid-1]！=x，則說明x肯定為第一個出現；若A[mid-1]=x，則要更新right = mid-1，因為此時第一個x肯定在[left, mid-1]之間，代碼如下：
//查找第一個等于x的位置
int findfirstX(int A[], int n, int x){
int left = 0, right = n-1;
int mid;
while(left <= right){
mid = left + ((right-left) >> 1);
if(A[mid] > x){
right = mid-1;
}else if(A[mid] < x){
left = mid + 1;
}else{
if(mid == 0 || A[mid-1] != x) return mid;
else right = mid-1;
}
}
return -1;
}
查找序列中最后一個等于給定值的元素
該問題和上面同樣的思路，要判斷mid是否為n-1，或者A[mid+1]即后一個是否為x，然后進行更新回傳，
//查找最后一個等于x的元素位置
int findlastX(int A[], int n, int x){
int left = 0, right = n-1, mid;
while(left <= right){
mid = left + ((right-left) >> 1);
if(A[mid] > x){
right = mid-1;
}else if(A[mid] < x){
left = mid + 1;
}else{
if(mid == n-1 || A[mid+1] != x) return mid;
else left = mid+1;
}
}
return -1;
}
查找序列中第一個大于等于x的元素的位置
思路和前面兩種類似，如果A[mid]小于要查找的值value，那要查找的值肯定在[mid+1, high]之間，如果A[mid] 大于等于給定的值x，要先看下這個mid=0 || A[mid-1] < x，則此時肯定時第一個大于等于x的值，否則A[mid-1]>x，則要找的值肯定在[left, mid-1]之間，所以更新right = mid-1;
//查找第一個大于等于x的元素位置
int Upperfind(int A[], int n, int x){
int left = 0, right = n-1, mid;
while(left <= right){
mid = left + ((right-left) >> 1);
if(A[mid] >= x){
if((mid==0) || (A[mid-1] < x)) return mid;
else right = mid-1;
}else{
left = mid+1;
}
}
}
查找序列中最后一個小于等于x的元素的位置
思路同上面一樣，代碼如下：
//查找最后一個小于等于x的元素位置
int boundfind(int A[], int n, int x){
int left =0, right = n-1, mid;
while(left <= right){
mid = left + ((right- left) >> 1);
if(A[mid] <= x){
if((mid==n-1) || (A[mid+1] > x)) return mid;
else left = mid+1;
}else{
right = mid-1;
}
}
}
查找序列中第一個大于x的元素的位置
//查找第一個大于x的元素位置
int findlargeX(int A[], int n, int x){
int left =0 ,right = n-1, mid;
while(left <= right){
mid = left + ((right- left) >> 1);
if(A[mid] > x){
if((mid==0) || (A[mid-1] < x)) return mid;
else right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
參考資料：
極客時間 王崢演算法課程：https://time.geekbang.org/column/article/42520
演算法筆記 胡凡 曾磊
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119217.html
標籤：其他