一.二分查找基本思想
在有序的序列裡，先将目标和中間的數值比較，如果大于中間數值，則在後半段的中間繼續比對；如果小于中間數值，則在前半段的中間繼續比對。以此類推，直至找到目标，或者結束查找沒有找到。
二.關鍵條件
(1)有序序列
(2)順序存儲結構
三.時間複雜度
O(logn)
四.優點和不足
優點是比較次數少，查找速度快，平均性能好；
缺點是要求待查表為有序表，且插入删除困難
五.代碼示例：（下面例子皆以升序為例）
1.最基本的二分查找：
int binarySearch(int arr[],int arr_L,int N)
{
int min=0;
int max=arr_L-1;
int mid=0;
while(min<=max)//注意這裡有等于=，不然會丢失邊界的情況
{
//mid=int(1.0/2*(min+max));//這裡有可能會産生溢出，而且需要強制類型轉換，不建議使用
mid=min+(max-min)/2;
if(N==arr[mid])
{
return mid;
}
else if(N<arr[mid])
{
max=mid-1;
}
else
{
min=mid+1;
}
}
return -1;
}
這裡有幾個問題需要注意：
1.循環判定的條件：min<=max(如果直接是min<max就會丢失邊界)
2.為了防止資料溢出：mid=min+(max-min)/2
3.當N!=arr[mid]時，min=mid+1,max=mid-1
2.遞歸實作二分查找
//遞歸二分查找
int binarySearch2(int arr[],int high,int low,int N)
{
//int mid=int(1.0/2*(high+low));
int mid=low+(high-low)/2;
if(low>high)
{
return -1;
}
if(N==arr[mid])
{
return mid;
}
else if(N>arr[mid])
{
low=mid+1;
return binarySearch2(arr,high,low,N);
}
else
{
high=mid-1;
return binarySearch2(arr,high,low,N);
}
}
需要注意的問題同上。
3.二分法的幾種變形
（1）查找目标值區域的左邊界（查找與目标值相等的第一個位置)(查找第一個不小于目标值數的位置)
//查找目标值區域的左邊界（查找與目标值相等的第一個位置)(查找第一個不小于目标值數的位置)
int binarySearch(int arr[],int arr_L,int N)
{
int min=0;
int max=arr_L-1;
int mid=0;
while(min<=max)//注意這裡有等于=，不然會丢失邊界的情況
{
//mid=int(1.0/2*(min+max));//這裡有可能會産生溢出，而且需要強制類型轉換
mid=min+(max-min)/2;
if(N<=arr[mid])
{
max=mid-1;
}
else
{
min=mid+1;
}
}
if(min<arr_L&&arr[min]==N)
{
return min;
}
else
{
return -1;
}
}
（2）查找目标值區域的右邊界（查找與目标值相等的最後一個位置)(查找最後一個不大于目标值數的位置)
//查找目标值區域的右邊界（查找與目标值相等的最後一個位置)(查找最後一個不大于目标值數的位置)
int binarySearch(int arr[],int arr_L,int N)
{
int min=0;
int max=arr_L-1;
int mid=0;
while(min<=max)//注意這裡有等于=，不然會丢失邊界的情況
{
//mid=int(1.0/2*(min+max));//這裡有可能會産生溢出，而且需要強制類型轉換
mid=min+(max-min)/2;
if(N>=arr[mid])
{
min=mid+1;
}
else
{
max=mid-1;
}
}
if(max>0&&arr[max]==N)
{
return max;
}
else
{
return -1;
}
}
(3)查找第一個大于目标值的數/查找比目标值大但是最接近目标值的數的位置（第二題變形）
int binarySearch(int arr[],int arr_L,int N)
{
int min=0;
int max=arr_L-1;
int mid=0;
while(min<=max)//注意這裡有等于=，不然會丢失邊界的情況
{
//mid=int(1.0/2*(min+max));//這裡有可能會産生溢出，而且需要強制類型轉換
mid=min+(max-min)/2;
if(N>=arr[mid])
{
min=mid+1;
}
else
{
max=mid-1;
}
}
return low<arr_L?low:-1;
}
注意此處就是大于目标值的最後一位，也就是max+1,也就是退出循環的 min
(4)查找最後一個小于目标值的數/查找比目标值小但是最接近目标值的數的位置（第（1）題變形）
int binarySearch(int arr[],int arr_L,int N)
{
int min=0;
int max=arr_L-1;
int mid=0;
while(min<=max)//注意這裡有等于=，不然會丢失邊界的情況
{
//mid=int(1.0/2*(min+max));//這裡有可能會産生溢出，而且需要強制類型轉換
mid=min+(max-min)/2;
if(N<=arr[mid])
{
max=mid-1;
}
else
{
min=mid+1;
}
}
return max>0?max:-1;
}
(6).旋轉數組（無重複項）
(什麼是旋轉數組：将一組有序的序列左移，将移出來的部分依次連接配接到原序列後邊(1 2 3 4 5--------->4 5 1 2 3))
int findMin(int arr[],int N)
{
int left=0;
int right=N-1;
int mid=0;
if(N==0)
{
return -1;
}
while(left<right)
{
mid=left+(right-left)/2;
if(arr[mid]>arr[right])
{
left=mid+1;
}
else
{
right=mid;
}
}
return arr[left];
}
和二分法的差別：（1）條件是right<left
(2)如果arr[mid]<arr[right]，說明前半部分有序，最小值在後半部分；反之，說明最小值在前半部分，最後left會指向最小項
(7)旋轉數組（有重複項）
int findMin(int arr[],int N)
{
int left=0;
int right=N-1;
int mid=0;
if(N==0)
{
return -1;
}
while(left<right)
{
mid=left+(right-left)/2;
if(arr[mid]>arr[right])
{
left=mid+1;
}
else if(arr[mid]<arr[right])
{
right=mid;
}
else
{
right--;
}
}
return arr[left];
}
差別就是當arr[mid]==arr[right]時，不知道最小值在右邊還是左邊，就讓right-1;
(8)旋轉序列中搜尋（不含重複項）
int search(int arr[],int arr_L,int N)
{
int left=0;
int right=arr_L-1;
int mid=0;
int offset,remid;
if(arr_L==0)
{
return -1;
}
while(left<right)
{
mid=left+(right-left)/2;
if(arr[mid]>arr[right])
{
left=mid+1;
}
else
{
right=mid;
}
}
offset=left;
left=0,right=arr_L-1;
while(left<=right)
{
mid=left+(right-left)/2;
remid=(mid+offset)%arr_L;
if(N==arr[remid])//arr[remid]為有序序列的中點值
{
return remid;
}
else if(N>arr[remid])
{
left=mid+1;//這裡需要特别注意
}
else
{
right=mid-1;
}
}
return -1;
}
先找到最小的值，即找到分界點，然後根據remid=(mid+offset)%len求得真實的mid位置，即arr[remid]是有序序列的中點，arr[mid]為目前序列的中點（旋轉數組），是以特别需要注意二分查找時left=mid+1,而不是left=remid+1;
不需要找分界點的方法：
int search(int arr[],int arr_L,int N)
{
int left=0;
int right=arr_L-1;
int mid=0;
if(arr_L==0)
{
return -1;
}
while(left<=right)
{
mid=left+(right-left)/2;
if(N==arr[mid])
{
return mid;
}
else if(arr[left]<=arr[mid])//從這裡直接判斷
{
if(N<arr[mid]&&N>=arr[left])
{
right=mid-1;
}
else
{
left=mid+1;
}
}
else if(arr[mid]<=arr[right])
{
if(N>arr[mid]&&N<=arr[right])
{
left=mid+1;
}
else
{
right=mid-1;
}
}
}
return -1;
}
（9）旋轉序列中搜尋（有重複項）
int search(int arr[],int arr_L,int N)
{
int left=0;
int right=arr_L-1;
int mid=0;
if(arr_L==0)
{
return -1;
}
while(left<=right)
{
mid=left+(right-left)/2;
if(N==arr[mid])
{
return mid;
}
else if(arr[mid]>arr[left])
{
if(N<arr[mid]&&N>=arr[left])
{
right=mid-1;//
}
else
{
left=mid+1;
}
}
else if(arr[mid]<arr[right])
{
if(N>arr[mid]&&N<=arr[right])
{
left=mid+1;
}
else
{
right=mid-1;
}
}
else
{
right--;
}
}
return -1;
}
待補充：二維數組中的查找
練習題目：
https://leetcode.com/problems/search-insert-position/description/
https://weiweiblog.cn/getnumberofk/
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii
https://weiweiblog.cn/minnumberinrotatearray/
https://leetcode.com/problems/search-in-rotated-sorted-array
https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
https://weiweiblog.cn/find2array/
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)