二分搜索法算法，也稱為二分搜索法和對數搜索算法，是壹種在有序數組中尋找特定元素的搜索算法。
基本思路:先確定要找的元素的範圍，然後逐漸縮小範圍，直到找到或找不到該元素。
0704二分搜索法*:給定壹個升序數組nums和壹個目標值，返回目標在數組中的位置，如果找不到，則返回-1。
例1:輸入為nums = [-1，0，3，5，9，12]，目標=9，輸出為4；
例2:輸入為nums = [-1，0，3，5，9，12]，目標=2，輸出為-1。
思路1:直接法。壹旦在循環體中找到要搜索的元素，就直接返回結果。
這種思路適合解決簡單的問題，即被搜索的元素性質簡單，數組中充滿了不重復的元素，相等的情況不等於比較的情況。
想法二:排除法。排除目標元素不能存在於循環體中的區間。
這種思想適用於解決復雜問題，比如尋找壹個數組中可能不存在的元素，可以用來尋找邊界問題。
題目描述:每輪遊戲中，會從1到N中隨機抽取壹個數字；猜錯了就分出來是大還是小。通過調用預定義的接口int guess(int num)可以得到猜測結果。當妳返回值* * * (-1，1或0)時有三種可能的情況，-1表示選中的數字小於猜測的數字，即picknum0表示妳猜對了，也就是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]，目標=5，輸出為2；
例2:輸入為nums=[1，3，5，6]，目標=2，輸出為1；
例3:輸入為nums=[1，3，5，6]，目標=7，輸出為4；
例4:輸入為nums=[1，3，5，6]，目標=0，輸出為0；
例5:輸入為nums=[1]，目標=0，輸出為0。
解決方案:在有序數組中找到第壹個大於或等於target的下標。
題目描述:給定壹個非負整數x，計算並返回x的算術平方根，由於返回類型為整數，所以只保留結果的整數部分，小數部分丟棄。不允許使用任何內置指數函數和運算符。例1:輸入為x=4，輸出為2；例2:輸入為x=8，輸出為2。說明:8的算術平方根是2.82842...由於返回類型是整數，小數部分將被截斷。
解決問題的思考:將其轉化為尋找滿足K 2的解
時間復雜度:o(log(x))；空間復雜度:O(1)。
題目描述:給出壹個按非遞減順序排列的整數數組，從數組中找出兩個數之和等於目標數target。該函數應該將這兩個數字的下標值作為長度為2的整數數組返回。數字下標從1開始計數，因此答案數組應該滿足1
解決方法:固定第壹個數字，找到它右邊的第二個數字，使第二個數字等於目標值減去第壹個數字。我以前做過壹次。
時間復雜度:o(nlog(n))；空間復雜度:O(1)。
標題描述:傳送帶上的包裹必須在d天內從壹個港口運輸到另壹個港口。傳送帶上第I個包裹的重量為weights[i]。每天都有包裹按重量順序裝在傳送帶上。裝載重量不會超過船的最大載重量。返回船只在d天內可以在傳送帶上交付所有包裹的最小運載能力。例1:輸入為weights = [1，2，3，4，5，6，7，8，9，10]，輸出為15；解釋:日1是1，2，3，4，5；第二天是6、7；第三天是8；第四天是9；第五天是10，所以最小負荷是15。例2:輸入為weights=[3，2，2，4，1，4]，D=3，輸出為6；解釋:日1是3，2；第二天是2和4；第三天是1，4；所以最小載荷是6。例3:輸入為weights = [1，2，3，1，1]，輸出為3。解釋:日1是1；第二天是2；第三天是3；第四天是1，1；所以最小載荷是3。
解題思路:二分搜索法轉化為判斷題。有壹個運載量的下限x ans，使得x >: =x ans，可以幾天送達，否則無法送達所有包裹。因為是順序發貨，所以發貨都是連續安排在同壹天。當這批包裹的重量大於承載量x時，需要取出最後壹個包裹，安排新的壹天，繼續遍歷。當遍歷整個數組時，獲得要運輸的最少天數。將最小待運天數與天數進行比較，如果小於等於天，則忽略二等分區間的右半部分；當它大於天時，二分法的左半區間被忽略。
時間復雜度:o(nlog(sum(w))；空間復雜度:O(1)。
標題描述:產品的每個版本都是基於上壹個版本開發的，所以錯誤版本之後的所有版本都是錯誤的。假設有n個版本[1，2，...，n]，並找出第壹個導致後面版本出錯的錯誤版本。可以調用boolisadvice (version)接口來確定單元測試中版本號version是否錯誤。實現壹個函數來查找第壹個錯誤的版本。您應該盡量減少調用API的次數。例1:輸入n=5，壞=4，輸出4；說明:調用is adversion(3)->；假的；調用(4)->真實；呼叫(5)->；沒錯。所以4是第壹個錯誤的版本。場景二:輸入n=1，壞=1，輸出1。
解決方法:將左右初始化為1和n，從中間開始二分搜索法。
時間復雜度:o(log(n))；空間復雜度:O(1)。
題目描述:整數數組nums按升序排列，數組中的值互不相同。在傳遞給函數之前，nums使用下標k (0
解決方案:二分搜索法適用於有序陣列。如果把數組從中間分開，肯定有壹些部分是按順序的。首先對mid進行劃分，看[left，mid]和[mid+1，right]哪個部分是有序的，根據有序部分改變二分搜索法的上下界，根據有序部分判斷目標是否在這個部分。
時間復雜度:o(log(n))；空間復雜度:O(1)。
題目描述:已知壹個長度為n的數組，事先按升序排列，經過1到n次旋轉，得到輸入數組。比如原數組nums=[0，1，2，4，5，6，7]改變後可能得到:如果旋轉四次，可以得到[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 [65438]。給出了壹個元素值不同的數組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 .二分搜索法，左邊界低，右邊界高，區間中點為pivot，最小值在此區間內。比較中點元素和右邊界元素。(1)中點元素<右邊界元素，中點在最小值的右邊，二分搜索法的右半部分可以忽略；(2)中點元素>右邊界元素，中點在最小值的左側，二分搜索法的左半部分可以忽略；因為數組不包含重復元素，並且當前長度不是1，所以它不會與high重合。如果長度為1，則二分搜索法可以結束。
時間復雜度:o(log(n))；空間復雜度:O(1)。