二次檢索演算法
① 二分搜索演算法
#include <stdio.h>
#include <stdlib.h>
int a[100]={1,2,3,5,12,12,12,15,29,55};//數組中的數（由小到大）
int k;
void found(int &x,int &y,int k) //在x與y之間，要找k
{
if(x>y)return;
int m=x+(y-x)/2;
if(a[m]==k)x=y=m;
else if(a[m]>k)found(x,y=m-1,k);//找左邊
else found(x=m+1,y,k);//找右邊
}
int main()
{ int i=0,j=9;
scanf("%d",&k);//輸入要找的數字k
found(i,j,k);//從數組a[0]到a[9]中找k
if(i==j)printf("a[%d]==%d ",i,k);
else printf("a[%d]==%d a[%d]==%d, k==%d ",j,a[j],i,a[i],k);
return 0;
}
② 二分查找演算法實現（圖解）與實例
當我們要從一個序列中查找一個元素的時候，二分查找是一種非常快速的查找演算法，二分查找又叫折半查找。
它對要查找的序列有兩個要求，一是該序列必須是有序的（即該序列中的所有元素都是按照大小關系排好序的，升序和降序都可以，本文假設是升序排列的），二是該序列必須是順序存儲的。
如果一個序列是無序的或者是鏈表，那麼該序列就不芹燃滑能進行二分查找。之所以被查找的序列要滿足這樣的條件，是由二分查找演算法的原理決定的。
二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
二分查找能應用於任何類型的數據，只要能將這些數據按照某種規則進行排序。然而，正因為它依賴於一個有序的集合，這使得它在處理那些頻繁插入和刪除操作的數據集時不太高效。這是因為，對於插入和操作來說，為了保證查找過程正常進行，必須保證數據集始終有序。相對於查找來說，維護一個有序數據集的代價更高。此外，元素必須存儲在連續的空間中。因此，當待搜索的集合是相對靜態的數據集時，此時使用二分查找段棚是最好的選擇。
二分查找演算法的原理如下：
二分查找之所以快速，是因為它在匹配不成功的時候，每次都能排除剩餘元素中一半嫌臘的元素。因此可能包含目標元素的有效范圍就收縮得很快，而不像順序查找那樣，每次僅能排除一個元素。
二分查找法實質上是不斷地將有序數據集進行對半分割，並檢查每個分區的中間元素。
此實現過程的實施是通過變數left和right控制一個循環來查找元素（其中left和right是正在查找的數據集的兩個邊界值）。
二分查找的時間復雜度取決於查找過程中分區數可能的最大值。對於一個有n個元素的數據集來說，最多可以進行O(㏒₂n)次分區。對於二分查找，這表示最終可能在最壞的情況下執行的檢查的次數：例如，在沒有找到目標時。所以二分查找的時間復雜度為O(㏒₂n)。
參考：
https://www.html.cn/qa/other/23018.html
https://www.cnblogs.com/idreamo/p/9000762.html
③ Task 04：數組二分查找
第8-10天打卡，附上 學習鏈接
二分查找演算法（Binary Search Algorithm），又稱為折半查找、對數查找演算法，是一種在有序數組中查找某一特定元素的搜索演算法。
基本思想：先確定待查找元素所在的區間范圍，再逐步縮小范圍，直到找到或找不到該元素為止。
0704 二分查找 *：給定一個升序的數組nums和一個目標值target，返回target在數組中的位置，如果找不到，則返回-1。
樣例1：輸入為nums=[-1, 0, 3, 5, 9, 12]，target=9，輸出為4；
樣例2：輸入為nums=[-1, 0, 3, 5, 9, 12]，target=2，輸出為-1。
思路1：直接法。一旦在循環體中找到該需查找的元素，就直接返回結果。
該種思路適合解決簡單題目，即查找的元素性質簡單，數組中都是非重復元素，且等於不等於的情況易於比較。
思路2：排除法。在循環體中排除目標元素一定不存在的區間。
該思路適合於解決復雜題目，如查找一個數組里可能不存在的元素，找邊界問題可使用該思路。
題目描述：每輪游戲，會從1到n隨機選擇一個數字；如果猜錯了，會告訴是大了還是小了。可以通過調用一個預先定義好的介面int guess(int num)來獲取猜測結果，返回值一共有3種可能的情況（-1,1或0），-1表示選出的數字比猜的數字小，即pick<num；1表示選出的數字比猜的數字大，即pick>num；0表示猜對了，即pick==num。返回我選出的數字。
樣例1：輸入為n=10，pick=6，輸出為6；
樣例2：輸入為n=1， pick=1，輸出為1；
樣例3：輸入為n=2，pick=1，輸出為1；
樣例4：輸入為n=2，pick=2，輸出為2。
解題思路：二分法。
題目描述：給定一個數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在數組中，返回它將會被按順序插入的位置。
樣例1：輸入為nums=[1, 3, 5, 6]，target=5，輸出為2；
樣例2：輸入為nums=[1, 3, 5, 6]，target=2，輸出為1；
樣例3：輸入為nums=[1, 3, 5, 6]，target=7，輸出為4；
樣例4：輸入為nums=[1, 3, 5, 6]，target=0，輸出為0；
樣例5：輸入為nums=[1]，target=0，輸出為0。
解題思路：在一個有序數組中找到第一個大於等於target的下標。
題目描述：給一個非負整數x，計算並返回x的算術平方根。由於返回類型是整數，結果只保留整數部分，小數部分將被捨去。不允許使用任何內置指數函數和算符。 樣例1：輸入為x=4，輸出為2； 樣例2：輸入為x=8，輸出為2。解釋：8的算術平方根是2.82842...，由於返回類型是整數，小數部分將被捨去。
解題思路：轉化為尋找滿足k 2 <=x的最大k值。二分查找，下界為0，上界粗略設定為x。每一步，通過比較中間元素mid的平方與x的大小關系，不斷調整上下界的范圍。
時間復雜度：O(log(x))； 空間復雜度：O(1)。
題目描述：給一個已按照 非遞減順序 排列的整數數組numbers，從數組中找出兩個數滿足相加之和等於目標數target。函數應該以長度為2的整數數組的形式返回這兩個數的下標值。numbers的下標從1開始計數，所以答案數組應當滿足1<=answer[0]<answer[1]<=numbers.length。可假設每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。 樣例1：輸入為numbers=[2, 7, 11, 15]，target=9，輸出為[2, 7]； 樣例2：輸入為numbers=[2, 3, 4]，target=6，輸出為[1, 3]； 樣例3：輸入為numbers=[-1, 0]，target=-1，輸出為[1, 2]。
解題思路：固定第一個數，在其右側尋找第二個數，使得第二個數等於目標值減去第一個數。（之前有做過一次）。
時間復雜度：O(nlog(n))； 空間復雜度：O(1)。
題目描述：傳送帶上的包裹必須在D天內從一個港口運送到另一個港口。傳送帶上的第i個包裹的重量為weights[i]。每一天，都會按照重量的順序往傳送帶上裝載包裹。裝載的重量不會超過船的最大運載重量。返回能在D天內將傳送帶上的所有包裹送達的船的最低運載能力。 樣例1：輸入為weights=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，D=5，輸出為15；解釋：第1天是1,2,3,4,5；第2天是6,7；第3天是8；第4天是9；第5天是10，所以最低載重為15。 樣例2：輸入為weights=[3, 2, 2, 4, 1, 4]，D=3，輸出為6；解釋：第1天是3,2；第2天是2,4；第3天是1,4；所以最低載重為6。 樣例3：輸入為weights=[1, 2, 3, 1, 1]，D=4，輸出為3。解釋：第1天是1；第2天是2；第3天是3；第4天是1,1；所以最低載重是3。
解題思路： 二分查找轉化為判定問題 。存在一個運載能力的下限x ans ，使得x>=x ans 時，可以在days天運送完，反之無法運送完所有包裹。因為有順序運載，連續安排在同一天進行運送。當這批包裹的重量大於運載能力x時，就需要將最後一個包裹拿出來，安排在新的一天，並繼續往下遍歷。當遍歷完整個數組後，就得到了最少需要運送的天數。使用 最少需要運送的天數 與days進行比較，小於等於days時，忽略二分的右半部分區間；當其大於days時，就忽略二分的左半部分區間。
時間復雜度：O(nlog(sum(w)))； 空間復雜度：O(1)。
題目描述：每個版本的產品都是基於之前的版本開發，因此錯誤的版本之後的所有版本都是錯誤的。假設有n個版本[1, 2, ..., n]，找出導致之後版本出錯的第一個錯誤版本。可以調用bool isBadVersion(version)介面來判斷版本號version是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。應該盡量減少對調用API的次數。 樣例1：輸入為n=5， bad=4，輸出為4；解釋：調用isBadVerison(3)->false；調用(4)->true；調用(5)->true。所以4是第一個錯誤的版本。 樣子2：輸入為n=1，bad=1，輸出為1。
解題思路：左右初始化為1和n，從中間開始二分查找。
時間復雜度：O(log(n))； 空間復雜度：O(1)。
題目描述：整數數組nums按升序排列，數組中的值互不相同。在傳遞給函數之前，nums在預先未知的某個下標k(0<=k<nums.length)上進行了旋轉，使數組變為[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標從0開始計數）。例如，[0, 1, 2, 4, 5, 6, 7]在下標3處經旋轉後可能變為[4, 5, 6, 7, 0, 1, 2]。給出旋轉後的數組nums和一個整數target，如果nums中存在這個目標值target，則返回它的下標，否則返回1。 樣例1：輸入為nums=[4, 5, 6, 7, 0, 1, 2]，target=0，輸出4； 樣例2：輸入為nums=[4, 5, 6, 7, 0, 1, 2]，target=3，輸出為-1； 樣例3：輸入為nums=[1]，target=0，輸出為-1。
解題思路：二分查找適用於有序數組。將數組從中間分開，肯定有一部分是有序的。首先mid分割，查看[left, mid]和[mid+1, right]哪個部分是有序的，根據有序的部分改變二分查找的上下界，根據有序的部分判斷target在不在這個部分。
時間復雜度：O(log(n))； 空間復雜度：O(1)。
題目描述：已知一個長度為n的數組，預先按照 升序 排列，經由1到n次旋轉後，得到輸入數組。例如，原數組nums=[0, 1, 2, 4, 5, 6, 7]在變化後可能得到：若旋轉4次，則可以得到[4, 5, 6, 7, 0, 1, 2]；若旋轉7次，則可以得到[0, 1, 2, 4, 5, 6, 7]。注意：數組[a[0], a[1], a[2], ..., a[n-1]]旋轉一次的結果為數組[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。給出一個元素值互不相同的數組nums，它原來是一個升序排列的數組，並進行了上述的多次旋轉。找出並返回數組中的最小元素。 樣例1：輸入為nums=[3, 4, 5, 1, 2]，輸出為1； 樣例2：輸入為nums=[4, 5, 6, 7, 0, 1, 2]，輸出為0； 樣例3：輸入為nums=[11, 13, 15, 17]，輸出為11。
解題思路：考慮數組中的最後一個元素x，在最小值右側的元素，值一定都嚴格小於x；左側一定都嚴格大於x。二分查找，左邊界為low，右邊界為high，區間的中點為pivot，最小值在該區間內。將中點元素與右邊界元素相比。 （1）中點元素<右邊界元素，則中點在最小值的右側，可以忽略二分查找的右半部分； （2）中點元素>右邊界元素，則中點在最小值的左側，可以忽略二分查找的左半部分； 因為數組不包含重復元素，且當前的長度不為1，則不會和high重合。如果長度為1，可以結束二分查找。
時間復雜度：O(log(n))； 空間復雜度：O(1)。