首先來簡介一下二分搜索算法,二分搜索是一種每次砍半的算法,最經典的案例當然是我們的二分查找算法,但是大部分人所認知的二分搜索都是必須要滿足這個 數組有序,才可以進行,其實不然,二分的本質邏輯是建立在"砍半",而砍半的本質就是你知道那一半一定沒有,而另一半不一定有的前提下,只要滿足了這一前提條件,那么你就可以盡可以進行二分…這個算法的時間復雜度是O(logN)
我們這個算法的系列將會長期更新,在遇見好題了之后就會加進來進行整理

情景一 : 二分查找

這個是二分最經典的情景,也就是在一個數組中進行每次砍半的查找元素
代碼實現如下

public static int myBinarySearch(int[] nums,int key){if(nums == null || nums.length == 0){System.out.println("無法進行搜索");return -1;}int left = 0;int right = nums.length - 1;int mid;while(left <= right){//請注意這里我們對于我們這個平均值的處理情況mid = left + ((right - left)>>1);if(nums[mid] > key){right = mid - 1;}else if(nums[mid] < key){left = mid + 1;}else{return mid;}}return -1;}

注意一下我們這里的求其平均值的操作,是利用位運算,其一是防止其溢出,其二是加快運算的速度,因為位運算的速度要遠大于除法運算…

情景二 : 找出一個 >= num 的最左側的位置

這個其實也是二分的邏輯,我們定義一個標記物 ans 初始化置為-1,當我們的mid滿足條件的時候,我們就將我們的ans置為 mid ,然后繼續二分,當不滿足條件的時候,我們就不進行操作,繼續二分,然后最后返回我們的 ans 標記物…
代碼實現如下 :

/***      情景二 : 找到 >= num 的最左側的位置*      這個基本的邏輯跟二分搜索法其實是一致的,但是也是有一定的差別,比如這個必須要搜索徹底才可以*      當每次滿足條件的時候,就進行 ans 的更新...直到left == right;**      可能你有疑問:為什么我們不進行 <= num 的最左側位置的查找 ...*      因為這個問題是沒有意義的..因為只需要判斷 nums[0] 跟 key的關系* @param nums : 待搜索的數組* @param key : 待定的查找元素* @return*/public static int findNumMaxLeft(int[] nums,int key){if(nums == null || nums.length == 0){System.out.println("無法進行搜索");return -1;}int left = 0;int right = nums.length - 1;int mid;int ans = -1;while(left <= right){mid = left +((right - left) >> 1);if(nums[mid] >= key){ans = mid;right = mid - 1;}else if(nums[mid] < key){left = mid + 1;}}return ans;}

情景三 : 找出一個 <= num 的最右側的位置

這個其實跟情景二是對稱的,原理是一致的,當滿足條件的時候記錄下來繼續進行二分,當不滿足條件的時候不進行記錄然后繼續進行二分,到二分到不能再次進行二分的情況之后,就返回我們的標記ans值…
代碼實現如下:

public static int findNumMinRight(int[] nums,int key){if(nums == null || nums.length == 0){System.out.println("無法進行搜索");return -1;}int left = 0;int right = nums.length - 1;int mid;int ans = -1;while(left <= right){mid = left +((right - left) >> 1);if(nums[mid] <= key){left = mid + 1;ans = mid;}else if(nums[mid] > key){right = mid - 1;}}return ans;}

leetcode 162 :尋找峰值

首先我們來分析一下這個題干,這個數組中相鄰的兩個元素都是不相等的,然后讓你返回其中的一個峰值(任意一個就可以),那這道題為什么可以進行二分呢…,我們來看體重的假設提示,我們假設 nums[-1] 和 nums[n] 都是 負無窮
首先我們判斷一下特殊的情況,假設我們的 第一個元素大于第二個元素,所以此時第一個元素就是局部的峰值(其實這里有點類似函數極值點的概念),對應的如果最后一個元素要大于倒數第二個元素,那么最后一個元素就是峰值

特殊情況的制約if(nums == null || nums.length == 0){System.out.println("這個數組不可能存在峰值");return -1;}//下面都是一些特殊情況的判斷...(端點處的極值問題)if(nums.length == 1){return 0;}if(nums[0] > nums[1]){return 0;}if(nums[nums.length-1] > nums[nums.length - 2]){return nums.length - 1;}

下面我們進行一般情況的分析

我們現在不滿足特殊條件,所以我們數組的走向是這樣的,那么因為我的開頭處是上升,終點位置是下降,所以中間的某個位置一定存在至少一個極值點(有點類似中值定理) 所以我們可以進行二分
判斷nums[mid] 和 nums[mid-1] 與nums[mid+1] 之間的關系…
而中值位置情況的只有以下四種

其中 1 2 4 都不是我們所需要的,所以要繼續進行二分搜索
所以我們可以寫出如下的代碼

int left = 1;int right = nums.length - 2;int mid;/*** 注意:* 這里的控制條件其實非常合理,在中點處一共只有四種情況,而這個循環的控制體系可以控制其中的三種無峰值的情況...*/while(left <= right){mid = left +((right - left) >> 1);if(nums[mid] < nums[mid - 1]){right = mid - 1;}else if(nums[mid] < nums [mid + 1]){left = mid + 1;}else{return mid;}}return -1;

下面是我們的完整代碼

public static int findPeakNumber(int[] nums){if(nums == null || nums.length == 0){System.out.println("這個數組不可能存在峰值");return -1;}//下面都是一些特殊情況的判斷...(端點處的極值問題)if(nums.length == 1){return 0;}if(nums[0] > nums[1]){return 0;}if(nums[nums.length-1] > nums[nums.length - 2]){return nums.length - 1;}//下面是普通的一個情況//其實有點類似數學的拉格朗日中值定理int left = 1;int right = nums.length - 2;int mid;/*** 注意:* 這里的控制條件其實非常合理,在中點處一共只有四種情況,而這個循環的控制體系可以控制其中的三種無峰值的情況...*/while(left <= right){mid = left +((right - left) >> 1);if(nums[mid] < nums[mid - 1]){right = mid - 1;}else if(nums[mid] < nums [mid + 1]){left = mid + 1;}else{return mid;}}return -1;}

leetcode 69 : x 的平方根

這就是一個典型的可以進行二分的題
這個題的核心邏輯跟我們第三個題 : 找出 >= num 的最右側位置是一致的
值得一提的是,我們這個題要控制我們的算數范圍,否則就會出現溢出的問題,下面就是我們的代碼解析…沒啥可說的了

/***  找出一個數的算術平方根向下取證的那個數然后返回* @param x : 待定的開方數* @return*/public static int mySqrt(int x){if(x == 0){return 0;}int left = 1;int right = x / 2;int mid;int ans = -1;while(left <= right){mid = left + ((right - left)>>1);if(mid <= x/mid){ans = mid;left = mid + 1;}else if(mid > x/mid){right = mid - 1;}}return ans;}

唯一要注意的一點就是,這里我們不可以用mid*mid <= x,要改成除法,用mid <= x / mid,否則這個題就會數值溢出導致出錯…