廢話(huà)不多說(shuō)，喊一句號(hào)子鼓勵(lì)自己：程序員永不失業(yè)，程序員走向架構(gòu)！本篇Blog的主題是【數(shù)組的二分查找】，使用【數(shù)組】這個(gè)基本的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，這個(gè)高頻題的站點(diǎn)是：CodeTop，篩選條件為：目標(biāo)公司+最近一年+出現(xiàn)頻率排序，由高到低的去?？蚑OP101去找，只有兩個(gè)地方都出現(xiàn)過(guò)才做這道題（CodeTop本身匯聚了LeetCode的來(lái)源），確保刷的題都是高頻要面試考的題。
名曲目標(biāo)題后，附上題目鏈接，后期可以依據(jù)解題思路反復(fù)快速練習(xí)，題目按照題干的基本數(shù)據(jù)結(jié)構(gòu)分類(lèi)，且每個(gè)分類(lèi)的第一篇必定是對(duì)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的介紹。
旋轉(zhuǎn)排序數(shù)組的最小數(shù)字【MID】
先來(lái)找最小值
題干
直接粘題干和用例
解題思路
通過(guò)題目描述我們知道，旋轉(zhuǎn)點(diǎn)后的排序子區(qū)間最大值也比旋轉(zhuǎn)點(diǎn)之前的排序子區(qū)間最小值小，最小值就是旋轉(zhuǎn)點(diǎn)，也就是數(shù)組的中間部分，所以我們使用碰撞雙指針從兩邊向中心搜索，不斷縮小搜索范圍：
- step 1：雙指針指向旋轉(zhuǎn)后數(shù)組的首尾，作為區(qū)間端點(diǎn)。
- step 2：若是區(qū)間中點(diǎn)值大于區(qū)間右界值，說(shuō)明中點(diǎn)在左側(cè)遞增區(qū)間，則最小的數(shù)字一定在中點(diǎn)右邊。
- step 3：若是區(qū)間中點(diǎn)值等于區(qū)間右界值，則是不容易分辨最小數(shù)字在哪半個(gè)區(qū)間，比如[1,1,1,0,1]，應(yīng)該逐個(gè)縮減右界。
- step 4：若是區(qū)間中點(diǎn)值小于區(qū)間右界值，說(shuō)明中點(diǎn)在右側(cè)遞增區(qū)間，則最小的數(shù)字一定在中點(diǎn)左邊。
- step 5：通過(guò)調(diào)整區(qū)間最后即可鎖定最小值所在。
代碼實(shí)現(xiàn)
給出代碼實(shí)現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：數(shù)組
輔助數(shù)據(jù)結(jié)構(gòu)：無(wú)
算法：二分查找
技巧：雙指針（碰撞雙指針）
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來(lái)自：
- 10 個(gè)數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列、散列表、二叉樹(shù)、堆、跳表、圖、Trie 樹(shù)
- 10 個(gè)算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動(dòng)態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動(dòng)窗口、中心擴(kuò)散
當(dāng)然包括但不限于以上文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-708424.html
import java.util.*;
public class Solution {
/**
* 代碼中的類(lèi)名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
*
*
* @param nums int整型一維數(shù)組
* @return int整型
*/
public int minNumberInRotateArray (int[] nums) {
// 1 入?yún)⑴袛?，參?shù)有效性校驗(yàn)
if (nums == null || nums.length == 0) {
return -1;
}
// 2 定義左右碰撞指針，找中點(diǎn)位置
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
// mid在左側(cè)遞增區(qū)間，最小值在mid右側(cè)[mid+1,right]
left = mid + 1;
} else if (nums[mid] < nums[right]) {
// mid在右側(cè)遞增區(qū)間，最小值為mid或mid左側(cè)[left,mid]
right = mid;
} else {
// 無(wú)法判斷，縮小右邊界
right--;
}
}
return nums[left];
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：O(log n)，二分法最壞情況對(duì)n取2的對(duì)數(shù)
空間復(fù)雜度：O(1)，常數(shù)級(jí)變量，無(wú)額外輔助空間
搜索旋轉(zhuǎn)排序數(shù)組【MID】
OK，接下來(lái)難度升級(jí)，不找最小值，找的是指定值
題干
直接粘題干和用例
解題思路
給出解題思路，最好有圖對(duì)于有序數(shù)組，可以使用二分查找的方法查找元素。但是這道題中，數(shù)組本身不是有序的，進(jìn)行旋轉(zhuǎn)后只保證了數(shù)組的局部是有序的，這還能進(jìn)行二分查找嗎？答案是可以的。
可以發(fā)現(xiàn)的是，我們將數(shù)組從中間分開(kāi)成左右兩部分的時(shí)候，一定有一部分的數(shù)組是有序的。拿示例來(lái)看，我們從 6 這個(gè)位置分開(kāi)以后數(shù)組變成了 [4, 5, 6] 和 [7, 0, 1, 2] 兩個(gè)部分，其中左邊 [4, 5, 6] 這個(gè)部分的數(shù)組是有序的，其他也是如此。
這啟示我們可以在常規(guī)二分查找的時(shí)候查看當(dāng)前 mid 為分割位置分割出來(lái)的兩個(gè)部分 [l, mid] 和 [mid + 1, r] 哪個(gè)部分是有序的，并根據(jù)有序的那個(gè)部分確定我們?cè)撊绾胃淖兌植檎业纳舷陆?，因?yàn)槲覀兡軌蚋鶕?jù)有序的那部分判斷出 target 在不在這個(gè)部分：
- 如果 [l, mid - 1] 是有序數(shù)組，且 target 的大小滿(mǎn)足 [nums[l],nums[mid])，則我們應(yīng)該將搜索范圍縮小至 [l, mid - 1]，否則在 [mid + 1, r] 中尋找。
- 如果 [mid, r] 是有序數(shù)組，且 target 的大小滿(mǎn)足 (nums[mid+1],nums[r]]，則我們應(yīng)該將搜索范圍縮小至 [mid + 1, r]，否則在 [l, mid - 1] 中尋找。
- 定理一：只有在順序區(qū)間內(nèi)才可以通過(guò)區(qū)間兩端的數(shù)值判斷target是否在其中。
- 定理二：判斷順序區(qū)間還是亂序區(qū)間，只需要對(duì)比 left 和 right 是否是順序?qū)纯?，left <= right，順序區(qū)間，否則亂序區(qū)間。
- 定理三：每次二分都會(huì)至少存在一個(gè)順序區(qū)間。
通過(guò)不斷的用Mid二分，根據(jù)定理二，將整個(gè)數(shù)組劃分成順序區(qū)間和亂序區(qū)間，然后利用定理一判斷target是否在順序區(qū)間，如果在順序區(qū)間，下次循環(huán)就直接取順序區(qū)間，如果不在，那么下次循環(huán)就取亂序區(qū)間。最終target一定會(huì)在一個(gè)順序區(qū)間，即使只有它一個(gè)元素。
代碼實(shí)現(xiàn)
給出代碼實(shí)現(xiàn)基本檔案
基本數(shù)據(jù)結(jié)構(gòu)：數(shù)組
輔助數(shù)據(jù)結(jié)構(gòu)：無(wú)
算法：二分查找
技巧：雙指針（碰撞雙指針）
其中數(shù)據(jù)結(jié)構(gòu)、算法和技巧分別來(lái)自：
- 10 個(gè)數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列、散列表、二叉樹(shù)、堆、跳表、圖、Trie 樹(shù)
- 10 個(gè)算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動(dòng)態(tài)規(guī)劃、字符串匹配算法
- 技巧：雙指針、滑動(dòng)窗口、中心擴(kuò)散
當(dāng)然包括但不限于以上
class Solution {
public int search(int[] nums, int target) {
// 1 入?yún)⑿ｒ?yàn)
if (nums == null || nums.length == 0) {
return -1;
}
// 2 定義雙指針
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
}
// 因?yàn)橹挥性谟行騾^(qū)間內(nèi)target的判斷才有意義，所以每次都在有序區(qū)間內(nèi)判斷，并且依據(jù)目標(biāo)值是否在有序區(qū)間內(nèi)，移動(dòng)左右指針
if (nums[left] <= nums[mid]) {
// 如果左邊是順序區(qū)間
if (target >= nums[left] && target < nums[mid]) {
// 如果目標(biāo)值在順序區(qū)間，在順序區(qū)間搜尋[left,mid-1]
right = mid - 1;
} else {
// 如果目標(biāo)值不在順序區(qū)間,在非順序區(qū)間搜尋[mid+1,right]
left = mid + 1;
}
} else {
// 如果右邊是順序區(qū)間
if (target > nums[mid] && target <= nums[right]) {
// 如果目標(biāo)值在順序區(qū)間，在順序區(qū)間搜尋[mid+1,right]
left = mid + 1;
} else {
// 如果目標(biāo)值不在順序區(qū)間,在非順序區(qū)間搜尋[left,mid-1]
right = mid - 1;
}
}
}
return -1;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：O(log n)，二分法最壞情況對(duì)n取2的對(duì)數(shù)
空間復(fù)雜度：O(1)，常數(shù)級(jí)變量，無(wú)額外輔助空間文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-708424.html
到了這里，關(guān)于【算法訓(xùn)練-數(shù)組 五】【二分查找】：旋轉(zhuǎn)排序數(shù)組的最小數(shù)字、旋轉(zhuǎn)排序數(shù)組的指定數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
