原文鏈接： 點(diǎn)這里
更多內(nèi)容就在我的個(gè)人博客 BlackBlog.tech 歡迎關(guān)注涝影！
謝謝大家！
本文源自LeetCode二分查找章節(jié)争占，通過(guò)本章節(jié)的練習(xí)對(duì)二分查找的基礎(chǔ)知識(shí)進(jìn)行掌握燃逻，同時(shí)能夠利用二分查找解決部分問(wèn)題。二分查找是一個(gè)效率非常高的算法臂痕，它充分利用了元素間的次序關(guān)系伯襟，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)握童。掌握二分查找對(duì)于提升代碼效率很有幫助逗旁。
LeetCode二分查找地址：https://leetcode-cn.com/explore/learn/card/binary-search/208/background/832/
本篇文章將介紹3個(gè)二分模版，同時(shí)完成十個(gè)例題舆瘪。在閱讀過(guò)程中，如果對(duì)三個(gè)模板的區(qū)別難以理解红伦，請(qǐng)務(wù)必完全閱讀完英古，這是一個(gè)需要逐步思考的過(guò)程。
給個(gè)目錄：
LeetCode704 二分查找
LeetCode69 x 的平方根
LeetCode374 猜數(shù)字大小
LeetCode33 搜索旋轉(zhuǎn)排序數(shù)組
LeetCode278 第一個(gè)錯(cuò)誤的版本
LeetCode75 尋找峰值
LeetCode159 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
LeetCode34 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
LeetCode658 找到 K 個(gè)最接近的元素
二分查找基礎(chǔ)知識(shí)
什么是二分查找
二分查找是計(jì)算機(jī)科學(xué)中最基本昙读、最有用的算法之一召调。 它描述了在有序集合中搜索特定值的過(guò)程。
二分查找中使用的術(shù)語(yǔ)：
目標(biāo) Target —— 你要查找的值
索引 Index —— 你要查找的當(dāng)前位置
左蛮浑、右指示符 Left唠叛，Right —— 我們用來(lái)維持查找空間的指標(biāo)
中間指示符 Mid —— 我們用來(lái)應(yīng)用條件來(lái)確定我們應(yīng)該向左查找還是向右查找的索引
二分查找原理
二分查找是一種在每次比較之后將查找空間一分為二的算法。每次需要查找集合中的索引或元素時(shí)沮稚，都應(yīng)該考慮二分查找艺沼。如果集合是無(wú)序的，我們可以總是在應(yīng)用二分查找之前先對(duì)其進(jìn)行排序蕴掏。
二分查找一般由三個(gè)主要部分組成：
預(yù)處理 —— 如果集合未排序障般，則進(jìn)行排序。
二分查找 —— 使用循環(huán)或遞歸在每次比較后將查找空間劃分為兩半盛杰。
后處理 —— 在剩余空間中確定可行的候選者挽荡。
二分查找是一個(gè)效率非常高的算法，它充分利用了元素間的次序關(guān)系即供，采用分治策略定拟，可在最壞的情況下用O(log n)完成搜索任務(wù)。掌握二分查找對(duì)于提升代碼效率很有幫助逗嫡。
復(fù)雜度
二分查找的時(shí)間復(fù)雜度：O(log n)青自，因?yàn)槎植檎沂峭ㄟ^(guò)對(duì)查找空間中間的值應(yīng)用一個(gè)條件來(lái)操作的株依，并因此將查找空間折半，在更糟糕的情況下性穿，我們將不得不進(jìn)行 O(log n) 次比較勺三，其中 n 是集合中元素的數(shù)目。
二分查找的空間復(fù)雜度：O(1)需曾，不需要任何其他額外空間吗坚。
LeetCode704 二分查找
我們先來(lái)一道最為基礎(chǔ)的二分查找題目，理解一下二分查找呆万。
本題為L(zhǎng)eetCode704 二分查找商源，屬于二分查找中最為基礎(chǔ)的練習(xí)。二分查找谋减，顧名思義牡彻，就是將數(shù)組一分為二，在左右兩邊查找出爹，確定元素區(qū)間之后再次一分為二庄吼，直至確定元素。
題目
給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target 严就，寫一個(gè)函數(shù)搜索 nums 中的 target总寻，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1梢为。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1
提示：
你可以假設(shè) nums 中的所有元素是不重復(fù)的渐行。
n 將在 [1, 10000]之間。
nums 的每個(gè)元素都將在 [-9999, 9999]之間铸董。
C++代碼
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left<=right){
int mid = (left+right)/2; //計(jì)算計(jì)算中間值
if(nums[mid]==target) return mid; //如果找到了target祟印，返回當(dāng)前的索引
if(nums[mid]<target) left = mid+1; //如果nums[mid]<target，證明正確的值在當(dāng)前位置的右邊
if(nums[mid]>target) right = mid-1; //如果nums[mid]>target粟害，證明正確的值在當(dāng)前位置的左邊
}
return -1;
}
};
體會(huì)
本題是二分查找最為基礎(chǔ)的題目蕴忆，對(duì)于理解二分查找非常重要。
二分查找 模版#1
模板 #1 是二分查找的最基礎(chǔ)和最基本的形式悲幅。這是一個(gè)標(biāo)準(zhǔn)的二分查找模板孽文，是非常基礎(chǔ)簡(jiǎn)單的二分查找夺艰。模板 #1 用于查找可以通過(guò)訪問(wèn)數(shù)組中的單個(gè)索引來(lái)確定的元素或條件芋哭。模版#1 不需要后處理，因?yàn)槊恳徊街杏舾保愣荚跈z查是否找到了元素减牺。如果到達(dá)末尾，則知道未找到該元素。
模版#1 對(duì)應(yīng)的例題為：
LeetCode69 x 的平方根
LeetCode374 猜數(shù)字大小
LeetCode33 搜索旋轉(zhuǎn)排序數(shù)組
模版#1 C++代碼
int binarySearch( vector<int> & nums, int target )
{
if ( nums.size() == 0 )
return(-1);
int left = 0, right = nums.size() - 1;
while ( left <= right )
{
/* Prevent (left + right) overflow */
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if ( nums[mid] < target ) left = mid + 1;
else right = mid - 1;
}
/* End Condition: left > right */
return(-1);
}
語(yǔ)法關(guān)鍵
初始條件：left = 0, right = length-1
終止：left > right
向左查找：right = mid-1
向右查找：left = mid+1
LeetCode69 x 的平方根
題目
實(shí)現(xiàn) int sqrt(int x) 函數(shù)拔疚。
計(jì)算并返回 x 的平方根肥隆，其中 x 是非負(fù)整數(shù)。
由于返回類型是整數(shù)稚失，結(jié)果只保留整數(shù)的部分栋艳，小數(shù)部分將被舍去。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說(shuō)明: 8 的平方根是 2.82842...,
由于返回類型是整數(shù)句各，小數(shù)部分將被舍去吸占。
C++代碼
class Solution {
public:
int mySqrt(int x){
int left = 0;
int right = x;
if (x <= 1) return x;
int ans= 0;
while(left<=right){
int mid = (right+left) /2; //計(jì)算中間值
if(x/mid >= mid ) {
left = mid+1; //如果mid*mid<=x 證明mid小了 left = mid+1
ans = mid; //當(dāng)前的mid作為ans
}
else right = mid-1; //否則right = mid-1
}
return ans;
}
};
體會(huì)
上述代碼采用二分查找的思路，與模版完全一致凿宾，注意每次計(jì)算的過(guò)程中要將mid存儲(chǔ)在ans中矾屯，因?yàn)槲覀儫o(wú)法通過(guò)mid*mid==x去判斷mid是否是正確值，所以我們將mid存儲(chǔ)在ans中初厚，最后返回件蚕。
該題還可以使用牛頓迭代法的思路進(jìn)行求解。
附代碼：
class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0;
double res = 1, pre = 0;
while (abs(res - pre) > 1e-6) {
pre = res;
res = (res + x / res) / 2;
}
return int(res);
}
};
LeetCode374 猜數(shù)字大小
題目
我們正在玩一個(gè)猜數(shù)字游戲产禾。 游戲規(guī)則如下：
我從 1 到 n 選擇一個(gè)數(shù)字排作。 你需要猜我選擇了哪個(gè)數(shù)字。
每次你猜錯(cuò)了亚情，我會(huì)告訴你這個(gè)數(shù)字是大了還是小了妄痪。
你調(diào)用一個(gè)預(yù)先定義好的接口 guess(int num)，它會(huì)返回 3 個(gè)可能的結(jié)果（-1势似，1 或 0）：
-1 : 我的數(shù)字比較小
1 : 我的數(shù)字比較大
0 : 恭喜！你猜對(duì)了僧著！
示例 :
輸入: n = 10, pick = 6
輸出: 6
C++代碼
int guess(int num);
class Solution {
public:
int guessNumber(int n) {
long left = 0;
long right = n;
while(left<=right){
long mid = (left+right)/2;
if(guess(mid)==0) return mid;
if(guess(mid)==1) left = mid+1;
if(guess(mid)==-1) right = mid-1;
}
return left;
}
};
體會(huì)
這個(gè)題完全就是大一的課后題履因，基礎(chǔ)二分查找問(wèn)題，與模版#1思路完全一致盹愚，比較大小的部分已經(jīng)在guess中封裝了栅迄，注意判斷好guess最后的返回值。
LeetCode33 搜索旋轉(zhuǎn)排序數(shù)組
題目
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)皆怕。
( 例如毅舆，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個(gè)給定的目標(biāo)值愈腾，如果數(shù)組中存在這個(gè)目標(biāo)值憋活，則返回它的索引，否則返回 -1虱黄。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素悦即。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1
C++代碼
class Solution {
public:
int search(vector<int> nums, int target) {
//對(duì)于特殊情況的判斷
if(nums.size()==0) return -1;
if(nums.size()==1 && nums[0]==target) return 0;
if(nums.size()==1 && nums[0]!=target) return -1;
int index= 0 ; //記錄軸點(diǎn)
int size = nums.size();//記錄下初始數(shù)組的長(zhǎng)度
for(int i=0;i<nums.size();i++){
if(nums[i]<nums[i-1]){
index = i; //找到軸點(diǎn)后結(jié)束循環(huán)
break;
}
nums.push_back(nums[i]); //在找到軸點(diǎn)之前，將軸點(diǎn)前數(shù)字依次放在數(shù)組尾部
}
int left = index; //left = 軸點(diǎn)
int right = nums.size()-1; //right = 數(shù)組當(dāng)前長(zhǎng)度-1
int ans = -1;//ans表示最終的位置
while(left<=right){
int mid = (left+right)/2; //計(jì)算中點(diǎn)
if(nums[mid]==target){
ans = mid; //如果nums[mid] == target
break;
}
if(nums[mid]<target) left = mid+1; //如果nums[mid]<target 修改left
if(nums[mid]>target) right = mid-1; //如果 nums[mid]>target 修改 right
if(nums[right] == target ) ans = right; //如果 nums[right] == target 將 ans修改為right 否則ans為-1
else ans = -1;
}
return ans % size;
}
};
體會(huì)
依舊是一個(gè)模版題辜梳，難度較低粱甫。我們之前說(shuō)過(guò)，二分查找的三個(gè)步驟作瞄，第一步是預(yù)處理 即如果集合未排序茶宵，則進(jìn)行排序。這個(gè)題將數(shù)組對(duì)某一軸點(diǎn)進(jìn)行了旋轉(zhuǎn)宗挥，需要進(jìn)行預(yù)處理乌庶。我們尋找到軸點(diǎn)，將數(shù)組修改為升序后属韧，預(yù)處理完成安拟，后續(xù)進(jìn)行二分即可。該題最后的處理有些類似模板2宵喂。
二分查找 模版#2
模板 #2 是二分查找的高級(jí)模板糠赦。它用于查找需要訪問(wèn)數(shù)組中當(dāng)前索引及其直接右鄰居索引的元素或條件。
查找條件需要訪問(wèn)元素的直接右鄰居锅棕。
使用元素的右鄰居來(lái)確定是否滿足條件拙泽，并決定是向左還是向右。
保證查找空間在每一步中至少有 2 個(gè)元素裸燎。
需要進(jìn)行后處理顾瞻。 當(dāng)你剩下 1 個(gè)元素時(shí)，循環(huán) / 遞歸結(jié)束德绿。 需要評(píng)估剩余元素是否符合條件荷荤。
模版#2 對(duì)應(yīng)的例題為：
LeetCode278 第一個(gè)錯(cuò)誤的版本
LeetCode75 尋找峰值
LeetCode159 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
模版#2 C++代碼
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size();
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.size() && nums[left] == target) return left;
return -1;
}
語(yǔ)法關(guān)鍵
初始條件：left = 0, right = length
終止：left == right
向左查找：right = mid
向右查找：left = mid+1
LeetCode278 第一個(gè)錯(cuò)誤的版本
題目
你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開(kāi)發(fā)新的產(chǎn)品移稳。不幸的是蕴纳，你的產(chǎn)品的最新版本沒(méi)有通過(guò)質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開(kāi)發(fā)的个粱，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的古毛。
假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本都许。
你可以通過(guò)調(diào)用 bool isBadVersion(version) 接口來(lái)判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)稻薇。實(shí)現(xiàn)一個(gè)函數(shù)來(lái)查找第一個(gè)錯(cuò)誤的版本。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)胶征。
示例:
給定 n = 5塞椎，并且 version = 4 是第一個(gè)錯(cuò)誤的版本。
調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true
所以睛低，4 是第一個(gè)錯(cuò)誤的版本忱屑。
C++代碼
class Solution {
public:
int firstBadVersion(int n) {
long left = 0;
long right = n;
while(left<right){
long mid = (left+right)/2; //計(jì)算中點(diǎn)
if(isBadVersion(mid)==false) left = mid+1; //如果mid是正常產(chǎn)品蹬敲，證明第一個(gè)錯(cuò)誤產(chǎn)品在右側(cè)
if(isBadVersion(mid)==true) right = mid; //如果mid是錯(cuò)誤產(chǎn)品，證明第一個(gè)錯(cuò)誤產(chǎn)品在是自己或者在左側(cè)
}
return left;
}
};
體會(huì)
題目非常簡(jiǎn)單莺戒，直接套用模板#2即可伴嗡。此題與模板#1的最大區(qū)別就在于，right不能修改為mid-1从铲，而必須修改為mid瘪校。因?yàn)楫?dāng)如果mid是錯(cuò)誤產(chǎn)品，無(wú)法判斷第一個(gè)錯(cuò)誤版本在mid之前名段，還是就是當(dāng)前mid阱扬。這是模板#2與模板#1的最大不同绘沉。
LeetCode75 尋找峰值
題目
峰值元素是指其值大于左右相鄰值的元素砸彬。
給定一個(gè)輸入數(shù)組 nums掏击，其中 nums[i] ≠ nums[i+1]灌曙，找到峰值元素并返回其索引。
數(shù)組可能包含多個(gè)峰值奸攻，在這種情況下准潭，返回任何一個(gè)峰值所在位置即可她君。
你可以假設(shè) nums[-1] = nums[n] = -∞静稻。
示例 1:
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素警没，你的函數(shù)應(yīng)該返回其索引 2。
示例 2:
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數(shù)可以返回索引 1振湾，其峰值元素為 2杀迹；
或者返回索引 5， 其峰值元素為 6押搪。
說(shuō)明:
你的解法應(yīng)該是 O(logN) 時(shí)間復(fù)雜度的树酪。
C++代碼
class Solution {
public:
int findPeakElement(vector<int>& nums) {
if(nums.size()==1) return 0;
long left = 0;
long right = nums.size()-1;
while(left<right){
long mid = (left+right)/2; //計(jì)算中間值
if(nums[mid]>nums[mid+1]) right = mid; //如果當(dāng)前值大于后一個(gè)值 證明當(dāng)前點(diǎn)可能是峰值點(diǎn)
if(nums[mid]<nums[mid+1]) left = mid+1; //如果當(dāng)前值小于后一個(gè)值 證明在這之后沒(méi)有峰值點(diǎn)
}
return left;
}
};
體會(huì)
直接套用模板2，此題與上一道題非常類似大州，如果當(dāng)前值大于后一個(gè)值 證明當(dāng)前點(diǎn)可能是峰值點(diǎn) right修改為mid续语，如果當(dāng)前值小于后一個(gè)值 證明在這之后沒(méi)有峰值點(diǎn)left修改為mid+1，最后返回left摧茴。
PS：如果此題要求求解最值绵载，則需要使用三分法埂陆。
LeetCode159 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
題目
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)苛白。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )焚虱。
請(qǐng)找出其中最小的元素购裙。
你可以假設(shè)數(shù)組中不存在重復(fù)元素。
示例 1:
輸入: [3,4,5,1,2]
輸出: 1
示例 2:
輸入: [4,5,6,7,0,1,2]
輸出: 0
C++代碼
class Solution {
public:
int findMin(vector<int> nums) {
if(nums.size()==1) return nums[0];
int left = 0;
int right = nums.size()-1;
while(left<right && nums[left]>nums[right] ){
int mid = (left+right)/2;
if(nums[left]<=nums[mid]) left = mid+1; //如果nums[left]<=nums[mid]鹃栽，即mid前的序列是遞增的躏率，則軸值一定不在mid之前，修改left=mid+1
else if(nums[left]>nums[mid]) right = mid;//如果nums[left]>nums[mid]，mid前的序列不是遞增的薇芝，則可能存在軸值蓬抄，切mid有可能是軸值，修改right=mid夯到。
}
return nums[left];
}
};
體會(huì)
依舊是一道模版題嚷缭。在確定mid之后，需要比對(duì)left與mid之間的關(guān)系耍贾，如果nums[left]<=nums[mid]阅爽，即mid前的序列是遞增的，則軸值一定不在mid之前荐开，修改left=mid+1付翁；如果nums[left]>nums[mid]，mid前的序列不是遞增的晃听，則可能存在軸值百侧，切mid有可能是軸值，修改right=mid杂伟。注意確定好邊界即可移层。
二分查找 模版#3
模板 #3 是二分查找的另一種獨(dú)特形式。它用于搜索需要訪問(wèn)當(dāng)前索引及其在數(shù)組中的直接左右鄰居索引的元素或條件赫粥。
搜索條件需要訪問(wèn)元素的直接左右鄰居观话。
使用元素的鄰居來(lái)確定它是向右還是向左。
保證查找空間在每個(gè)步驟中至少有 3 個(gè)元素越平。
需要進(jìn)行后處理频蛔。 當(dāng)剩下 2 個(gè)元素時(shí)，循環(huán) / 遞歸結(jié)束秦叛。 需要評(píng)估其余元素是否符合條件晦溪。
模版#3 對(duì)應(yīng)的例題為：
LeetCode34 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
LeetCode658 找到 K 個(gè)最接近的元素
模版#3 C++代碼
int binarySearch(vector<int>& nums, int target){
if (nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
語(yǔ)法關(guān)鍵
初始條件：left = 0, right = length-1
終止：left + 1 == right
向左查找：right = mid
向右查找：left = mid
LeetCode34 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
題目
給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target挣跋。找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置三圆。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。
如果數(shù)組中不存在目標(biāo)值避咆，返回 [-1, -1]舟肉。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
C++代碼
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0) return {-1,-1};
int left = 0;
int right = nums.size()-1;
while(left<right){
int mid = (left+right)/2;
if(nums[mid]==target) { //如果找到target 只需要向前向后搜索這個(gè)序列 找到起點(diǎn)和終點(diǎn)即可
int I=mid;
int j=mid;
while(nums[i+1]==target && i<nums.size()-1) i=i+1;
while(nums[j-1]==target && j>0) j = j-1;
return{j,i};
}
if(nums[mid]<target) left = mid+1; //如果nums[mid]<target 說(shuō)明target在mid的右側(cè)
else if(nums[mid]>target) right = mid-1; //如果nums[mid]>target 說(shuō)明target在mid的左側(cè)
}
return{-1,-1};
}
};
體會(huì)
做這個(gè)題的時(shí)候很想將模版#3套用進(jìn)去，但是沒(méi)有成功查库。這個(gè)題使用的是比較經(jīng)典的二分思路路媚。本次需要尋找對(duì)應(yīng)序列的起點(diǎn)與終點(diǎn)，所以當(dāng)我們找到一個(gè)target的值時(shí)樊销，要向前向后進(jìn)行搜索確定序列的起點(diǎn)終點(diǎn)整慎。
LeetCode658 找到 K 個(gè)最接近的元素
題目
給定一個(gè)排序好的數(shù)組脏款，兩個(gè)整數(shù) k 和 x，從數(shù)組中找到最靠近 x（兩數(shù)之差最锌阍啊）的 k 個(gè)數(shù)撤师。返回的結(jié)果必須要是按升序排好的。如果有兩個(gè)數(shù)與 x 的差值一樣拧揽，優(yōu)先選擇數(shù)值較小的那個(gè)數(shù)丈氓。
示例 1:
輸入: [1,2,3,4,5], k=4, x=3
輸出: [1,2,3,4]
示例 2:
輸入: [1,2,3,4,5], k=4, x=-1
輸出: [1,2,3,4]
說(shuō)明:
k 的值為正數(shù)，且總是小于給定排序數(shù)組的長(zhǎng)度强法。
數(shù)組不為空万俗，且長(zhǎng)度不超過(guò) 104
數(shù)組里的每個(gè)元素與 x 的絕對(duì)值不超過(guò) 104
C++代碼
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left =0;
int right = arr.size()-k; //為了防止越界，將right定為arr.size()-k饮怯，做預(yù)處理闰歪。
while(left<right){
int mid = (left+right)/2;
if(abs(arr[mid]-x)<=abs(arr[mid+k]-x)){ //比較arr[mid]與x的差值 與 arr[mid+k]與x的差值，如果abs(arr[mid]-x)<=abs(arr[mid+k]-x)蓖墅，證明左側(cè)離x更接近库倘，否則右側(cè)與x更接近。
right = mid;
}
else left = mid+1;
}
return vector<int>(arr.begin()+left, arr.begin() + left+k); //返回結(jié)果的時(shí)候同樣要做處理论矾。
}
};
體會(huì)
本題依舊沒(méi)有用到模版#3（尷尬＝挑妗），采用類似模版#2的思路贪壳，但本題的特殊之處在于預(yù)處理和后處理饱亿。預(yù)處理為了防止越界，將將right定為arr.size()-k闰靴，返回結(jié)果時(shí)返回的事[left,left+k]這一段序列彪笼。
本題使用二分的思路，我們要找與x最接近的k個(gè)數(shù)蚂且，每次計(jì)算出mid后配猫，比較arr[mid]與x的差值 與 arr[mid+k]與x的差值，如果abs(arr[mid]-x)<=abs(arr[mid+k]-x)杏死，證明左側(cè)離x更接近泵肄，更新right；否則右側(cè)與x更接近淑翼，更新left腐巢。
總結(jié)
（圖片源自LeetCode）
三個(gè)模版的主要差異在于左、中窒舟、右索引的分配系忙，循環(huán)或遞歸終止條件诵盼，后處理惠豺。
二分查找是非常常用的算法银还，真實(shí)應(yīng)用中，我們并不需要死記硬背這三個(gè)模版洁墙，更重要的是通過(guò)這三個(gè)模版理解二分搜索蛹疯，在實(shí)際應(yīng)用中，仔細(xì)確定查找邊界热监、遞歸范圍捺弦，一般便可以解決問(wèn)題。
