二分查找.png
非递归版本
int binarySearch(const vector<int>& vec, int targetNum)
{
int lo = 0;
int hi = vec.size()-1;
while(lo <= hi) {
int mid = (hi + lo) / 2; // mid=lo+(hi-lo)/2 这样写还可以防止溢出
if (vec[mid] == targetNum)
return mid;
else if (vec[mid] < targetNum)
lo = mid + 1;
else if (vec[mid] > targetNum)
hi = mid - 1;
}
return -1;
// return lo lo是该数据应该插入的位置。
}
递归版本
int binarySearch(const vector<int>& vec, int lo, int hi, int targetNum)
{
if (lo <= hi)
return -1;
int mid = (hi + lo)/2;
if (vec[mid] < targetNum)
return binarySearch(vec, mid+1, hi, targetNum);
else if (vec[mid] > targetNum)
return binarySearch(vec, lo, mid-1, targetNum);
else
return mid;
}
对二分查找分析
-
在N个有序数组中，进行二分查找最多需要(log2N + 1)次比较(无论是否成功)
总共有n个元素，渐渐分下去就是
n，n/2，n/4，.... n/(2^k)（接下来操作元素的个数），其中k就是循环 的次数，直到n/2^k=1/2，可得k = log2n + 1,（是以2为底，n的对数）所以时间复杂度可以表示O(h)=O(log2n)
35. 搜索插入位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int startIndex = 0;
int endIndex = nums.size() - 1;
int midIndex = 0;
while(startIndex <= endIndex)
{
auto midIndex = startIndex + (endIndex - startIndex) / 2;
if (nums[midIndex] == target)
return midIndex;
else if (nums[midIndex] > target)
endIndex = midIndex - 1;
else if (nums[midIndex] < target)
startIndex = midIndex + 1;
}
return startIndex;
}
};
367. 有效的完全平方数
- 暴力
- 二分查找
class Solution { public: bool isPerfectSquare(int num) { int lo = 1; int hi = num; while(lo <= hi) { int mid = lo + (hi - lo)/2; // 可以用>> if (mid * mid == num) // 这里注意溢出 return true; else if (mid * mid > num) hi = mid - 1; else lo = mid + 1; } return false; } }; - 数学定理
1 + 3 + 5 + ... + (2n - 1) = n ^ 2class Solution { public: bool isPerfectSquare(int num) { int i = 1; while(num > 0) { num -= i; i += 2; } return num == 0; } }; - 牛顿迭代法
牛顿迭代法参见 https://www.cnblogs.com/qlky/p/7735145.htmlclass Solution { public: bool isPerfectSquare(int num) { if (num == 1) { return true; } int i = num / 2; while((double)i * i > num) { i = (i + num / i) / 2; } return i * i == num; } };
278. 第一个错误的版本
场景一：isBadVersion(mid) => false
1 2 3 4 5 6 7 8 9
G G G G G G B B B G = 正确版本，B = 错误版本
| | |
left mid right
场景二：isBadVersion(mid) => true
1 2 3 4 5 6 7 8 9
G G G B B B B B B G = 正确版本，B = 错误版本
| | |
left mid right
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right)
{
int mid = left + (right - left) / 2;
if (isBadVersion(mid))
right = mid;
else
left = mid + 1;
}
return left;
}
};
数组中出现次数超过一半的数字
在排序数组中查找元素的第一个和最后一个位置
- 线性扫描
从左到右，从右到左 - 二分
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int start = findStartIndex(nums, 0, nums.size()-1, target); int end = findEndIndex(nums, 0, nums.size()-1, target); return vector<int>{start, end}; } int findStartIndex(const vector<int>& nums, int lo, int hi, int target) { while(lo <= hi) { int mid = lo + (hi-lo)/2; if (nums[mid] == target) { if (mid != 0) { if (nums[mid-1] != target) return mid; else hi = mid - 1; } else { return 0; } } else if (nums[mid] > target) { hi = mid - 1; } else if (nums[mid] < target) { lo = mid + 1; } } return -1; } int findEndIndex(const vector<int>& nums, int lo, int hi, int target) { while(lo <= hi) { int mid = lo + (hi-lo)/2; if (nums[mid] == target) { if (mid != nums.size()-1) { if (nums[mid+1] != target) return mid; else lo = mid + 1; } else { return nums.size()-1; } } else if (nums[mid] > target) { hi = mid - 1; } else if (nums[mid] < target) { lo = mid + 1; } } return -1; } };
50. Pow(x, n)
153. 寻找旋转排序数组中的最小值
- 暴力搜索整个数组，找出最小值
- 二分法
网友评论