leetcode演算法之二分查找
今天來盤一盤 ** 二分查找 ** 這類題目
程式碼採用**C++**實現
使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1
二分查找
二分查找是針對一個排序列表,每次利用中間元素折半去掉部分元素,減少重複的查找遍歷.
- 對於一個排序數組nums,查找指定的一個數字target,採用二分查找的解題思路
- 利用target與nums數組的中間元素相比較,
- 如果target> nums[mid],說明target在數組的後半部分,
- 如果target < nums[mid], 說明target在數組的前半部分
- 如果target == nums[mid], 找到target.
二分查找的典型解題思路模板程式碼:
int binary_search(vector<int>& nums, int target){
int l = 0, r = nums.size() - 1;
while (l <= r){
int mid = l + (r - l) / 2; // 直接採用(r+l)/2. 容易出現整形溢出
// 找到對應的元素,返回索引
if (nums[mid] == target) return mid;
// target比中間值大,說明存在數組後半部分
else if (nums[mid] < target)
l = mid + 1;
// target小, 說明存在數組的前半部分.
else
r = mid - 1;
}
return -1;
}
兩個非常困擾而且易錯的細節點:
- while循環的判斷條件是
l<r還是l<=r - 當target != nums[mid]時, 使用
mid還是mid (+或者-) 1
解決這兩個問題的只需要考慮清楚,查找區間的封閉情況, 例如對於上邊寫的程式碼,採用的方式為(左右均為閉區間)[l, r], 因此決定了循環判斷條件為l<=r. 同時 l = mid + 1與r = mid - 1, 在過程中始終保持全閉區間的情況不變
當然程式碼也可以採用左開右閉或者左閉右開的區間進行查找,然後判斷需要如何更改這兩個問題.
- 69 x 的平方根 (Easy)
- 744 尋找比目標字母大的最小字母 (Easy)
- 278 第一個錯誤的版本 (Easy)
- 540 有序數組中的單一元素 (Medium)
- 153 尋找旋轉排序數組中的最小值 (Medium)
- 34 在排序數組中查找元素的第一個和最後一個位置(medium)
69 x 的平方根 (Easy)
- 題解: 二分查找
- 全閉區間進行搜索
- 注意在計算過程中,直接平方會導致int溢出,需要轉換為double,或者long long
class Solution {
public:
int mySqrt(int x) {
// 採用二分查找
// 查找區間為[l, r]
int l=0, r=x/2;
while (l <= r){
int mid = l + (r - l) / 2;
double pow1 = static_cast<double>(mid) * mid;
double pow2 = static_cast<double>(mid + 1) * (mid + 1);
if (pow2 == x) return mid + 1;
else if (pow1 == x || (pow1 < x && pow2 > x)) return mid;
else if (pow1 > x)
r = mid - 1;
else
l = mid + 1;
}
return l;
}
};
744 尋找比目標字母大的最小字母 (Easy)
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
if (target >= *(letters.end() - 1)) return *(letters.begin());
// 全閉區間
int l = 0, r = letters.size() - 1;
while (l <= r){
int mid = l + (r - l) / 2;
if (target < letters[mid])
r = mid - 1;
else if (target >= letters[mid])
l = mid + 1;
}
return letters[l];
}
};
278 第一個錯誤的版本 (Easy)
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
// 直接二分即可,找到第一個為false的版本
// 全閉區間
int l = 1, r = n;
while (l <= r){
int mid = l + (r - l) /2 ;
if (isBadVersion(mid))
r = mid - 1;
else
l = mid + 1;
}
return l;
}
};
540 有序數組中的單一元素 (Medium)
- 題解: 二分查找
- 這道題直接判斷中間元素左右兩側的子數組哪一部分是奇數,說明單一元素就存在對應的部分
- 如果mid後半部分的數組是偶數:
-
- 那麼如果mid與mid+1位置的元素相等, 那麼去掉這倆元素後,後半部分就是奇數,說明單一元素存在右半部分, l = mid + 2
-
- 如果mid與mid – 1位置相等,那麼單一元素存在左半部分, r = mid – 2
- 同理分析mid的後半部分是奇數.
- 如果兩側均為偶數,那麼mid即為待查找的單一元素.
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
// 二分查找
// mid為數組中間的元素索引
// 如果mid與後邊或者前邊的元素相等, 那麼判斷哪一側是奇數就說明在哪一側
// 如果mid剛好就是單獨的元素,那麼直接返回即可
int l = 0, r = nums.size() - 1;
while (l < r){
int mid = l + (r - l) / 2;
// 後半部分是偶數
bool second_even = ((r - mid) % 2 == 0);
if (nums[mid + 1] == nums[mid]){
if (second_even)
l = mid + 2;
else
r = mid - 1;
}
else if (nums[mid] == nums[mid - 1]){
if (second_even)
r = mid - 2;
else
l = mid + 1;
}
else
return nums[mid];
}
return nums[l];
}
};
153 尋找旋轉排序數組中的最小值 (Medium)
- 題解1: 簡單順序查找
- 遍曆數組, 如果nums[i] > nums[i+1] return num[i+1]
- 如果遍歷完全沒有找到,就說明nums[0]是最小的元素.
class Solution {
public:
int findMin(vector<int>& nums) {
// 順序查找, 如果前邊元素,大於後邊,那麼就找到了對應的元素
for (int i = 0; i < nums.size() - 1; i++){
if (nums[i] > nums[i+1])
return nums[i+1];
}
return nums[0];
}
};
- 題解2: 二分查找
- 採用中間元素與首尾元素進行對比的方式
- 如果中間元素大於數組尾元素,說明反轉點在mid的右邊
- 如果中間元素小於數組的尾部元素. 說明反轉點在mid或者在mid的左邊
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
};
34 在排序數組中查找元素的第一個和最後一個位置(medium)
- 題解: 順序查找
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 直接順序查找
int l = 0, r = nums.size() - 1;
vector<int> res;
while (l <nums.size() && nums[l] != target)
l++;
while (r > 0 && nums[r] != target )
r--;
if (l != nums.size())
return {l, r};
else
return {-1, -1};
}
};
- 題解2: 二分查找
- 首先利用二分查找,找到對應的target
- 然後順序往左右擴展找到對應的邊界
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
// 使用二分查找,找到對應元素, 然後左右遍歷得到兩個坐標
int index = -1;
while (l <= r){
int mid = l + ( r - l ) / 2;
//找到對應的元素索引
if (nums[mid] == target){
index = mid;
break;
}
else if(nums[mid] < target)
l = mid + 1;
else
r = mid - 1;
}
// 沒有找到對應的索引
if (index == -1)
return {-1, -1};
int left = index, right = index;
// 向左擴展,找到元素左邊界
while (left >= 0 && nums[left] == target )
left--;
// 向右擴展找到有邊界
while (right < nums.size() && nums[right] == target)
right++;
return {left + 1, right - 1};
}
};
更多分類刷題資料
-
微信公眾號： 小哲AI
-
GitHub地址： //github.com/lxztju/leetcode-algorithm
-
csdn部落格： //blog.csdn.net/lxztju
-
知乎專欄： 小哲AI
-
AI研習社專欄：小哲AI
