第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)。