二分查找.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 + lo // 这样写还可以防止溢出
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)
二分查找局限性：
- 二分查找依赖的是顺序表结构，简单点说就是数组
- 二分查找针对的是有序数据
- 再次，数据量太小不适合二分查找
如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。 - 数据量太大也不适合二分查找
比如，我们有 1GB 大小的数据，如果希望用数组来存储，那就需要 1GB 的连续内存空间。
如何在 1000 万个整数中快速查找某个整数？每个数据大小是 8 字节，内存限制是100MB
最简单的办法就是将数据存储在数组中，内存占用差不多是 80MB，符合内存的限制。先对这 1000 万数据从小到大排序，然后再利用二分查找算法。
大部分情况下，用二分查找可以解决的问题，用散列表、二叉树都可以解决。但是，实际上，不管是散列表还是二叉树，都会需要比较多的额外的内存空间。如果用散列表或者二叉树来存储这 1000 万的数据，用 100MB 的内存肯定是存不下的，所以这里不适合用这2种数据结构。
4个变体
image.png
- 查找第一个值等于给定值的元素
public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] > value) { high = mid - 1; } else if (a[mid] < value) { low = mid + 1; } else { if ((mid == 0) || (a[mid - 1] != value)) return mid; else high = mid - 1; } } return -1; } - 查找最后一个值等于给定值的元素
else { if ((mid == n - 1) || (a[mid + 1] != value)) return mid; else low = mid + 1; } - 查找第一个大于等于给定值的元素
- 查找最后一个小于等于给定值的元素
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;
}
};
数组中出现次数超过一半的数字
34 在排序数组中查找元素的第一个和最后一个位置
- 线性扫描
从左到右，从右到左 - 二分
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. 寻找旋转排序数组中的最小值
- 暴力搜索整个数组，找出最小值
- 二分法
