二分法
中心思想：
對于有一定順序的陣列找里面的特殊值，將陣列分為2部分，這個特殊值只能在其中一部分里，陣列的兩部分分別是low-mid和mid-high，如果判斷出特殊值在low-mid中，則high=mid(+1/-1)，如果判斷出特殊值在mid-high中，則low=mid(+1/-1)，其中mid=low+(high-low)/2，然后繼續重新判斷，
重點：
劃分 [low, mid] 與 [mid + 1, high] ，mid 被分到左邊，對應 int mid = low + (high-low) / 2； 一般回傳low
while里是hi>lo
對于特殊例子，需要單獨計算
基礎代碼：
class Solution {
public:
int Number(vector<int>& nums) {
int lo = 0;
int hi = nums.size() - 1;
while (hi>lo) {
int mid = lo + (hi - lo) / 2;
if (mid == nums[mid]) //根據特殊值的特點設定條件
lo = mid + 1;
else
hi = mid;
}
return nums[lo];
}
};題1：
答案：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int lo = 0;
int hi = nums.size() - 1;
if (target > nums[hi]) //特殊情況
return nums.size();
if (nums.size() == 0) //特殊情況
return 0;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1;
else
hi=mid;
}
return lo ;
}
};題2：
、
答案：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int lo = 0;
int hi = nums.size()-1;
if (hi < 0) return{ -1,-1 }; //特殊情況
//找左邊界,定位在第一個target上
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (target > nums[mid])
lo = mid + 1;
else
hi = mid;
}
int leftdex = lo;
lo = 0;
hi = nums.size() - 1;
//找右邊界，定義在最后一個target的后邊的一個元素
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (target >= nums[mid])
lo = mid+1;
else
hi = mid;
}
int rightdex = lo-1;
if (nums[leftdex] != target) //特殊情況
return{ -1,-1 };
int part = nums.size() - 1;
if ( nums[nums.size() - 1] == target) return{ leftdex,part }; //特殊情況
return{ leftdex,rightdex};
}
};題3：
答案：
class Solution {
public:
int minArray(vector<int>& numbers) {
int lo = 0;
int hi = numbers.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (numbers[mid] > numbers[hi])
lo = mid + 1;
else if (numbers[mid] > numbers[hi])
hi = mid;
else
hi--;
}
return numbers[lo];
}
};題4：
答案：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int lo = 0;
int hi = nums.size() - 1;
if (nums[0] == 1) return 0;
if (nums[nums.size() - 1] == nums.size() - 1) return nums.size();
while (hi>lo) {
int mid = lo + (hi - lo) / 2;
if (mid == nums[mid])
lo = mid + 1;
else
hi = mid;
}
return nums[lo] - 1;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/223752.html
標籤：python
上一篇：JAVA中的Date類
下一篇：opencv2學習筆記（1）