部分图文参考于:代码随想录 - 二分查找,本文仅作为个人学习使用,如有侵权,请联系删除。
1.概念
二分查找也称折半查找(Binary Search),是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知,运用二分搜索的前提是数组必须是有序的,这里需要注意的是,我们的输入不一定是数组,也可以是数组中某一区间的起始位置和终止位置。
2.注意点
● 二分查找的基础条件:数组是有序数组。二分查找的循环中,坚持循环不变量的原则。
● while中left与right之间的比较: <= 还是 <?
● 不同写法对应了right移动时的不同位置:right = mid - 1;还是right = mid;?
● 防溢出:int mid = left + (right - left) / 2;等同于int mid = (left + right) / 2;
3.题目1★: 704.二分查找
3.1.注意点
二分查找前提:1.数组为有序数组。2.数组中无重复元素。
循环不变量规则:在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作。
3.2.思路
将给定的target值与数组中间位置的元素比较:
● 如果相等,则查找成功,返回元素所在的位置。
● 如果不等,则需要查找的元素在中间元素以外的前半部分或是后半部分。
在缩小的范围内,以相同的方式进行查找,如此反复,直到找到为止;或是确定数组中没有所需查找到元素,查找不成功,返回查找失败的信息。
根据边界条件的不同,主要分为[left, right]和[left, right)两种写法。
3.3.解法1:二分查找[left, right]
● while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=。
● if (nums[mid] > target) right 要赋值为 mid - 1,因为当前这个nums[mid]一定不是target,那么接下来要查找的左区间结束下标位置就是 mid - 1。
● 例如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; //[left, right]
while (left <= right) { //左闭右闭区间 [left, right]
int mid = left + (right - left) / 2; //等同于(left+right)/2,防溢出
if (nums[mid] < target) { //向右查找 [mid + 1, right]
left = mid + 1;
}
else if (nums[mid] > target) { //向左查找 [left, mid - 1]
right = mid - 1;
}
else { //nums[mid] == target,返回mid
return mid;
}
}
return -1; //找不到便返回-1
}
};
● 时间复杂度:\(O(logn)\)
● 空间复杂度:\(O(1)\)
3.4.解法2:二分查找[left, right)
● 区间为[left, right)时,while(left < right){};因为当left与right相等的情况在区间[left, right)没有意义。
● target > nums[mid],修改left为mid + 1,在右区间继续查找,所查找区间为[mid + 1, right)。target < nums[mid],修改right为mid,在左区间继续查找,所查找的区间为[left, mid),下一个查询区间不会比较nums[mid]。
● 在数组:1,2,3,4,7,9,10中查找元素2,如图所示:(注意和法一的区别)
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size(); //[left, right)
while (left < right) { //左闭右开区间 [left, right)
int mid = left + (right - left) / 2; //等同于(left+right)/2,防溢出
if (nums[mid] < target) { //向右查找 [mid + 1, right)
left = mid + 1;
}
else if (nums[mid] > target) { //向左查找 [left, mid)
right = mid;
}
else { //nums[mid] == target,返回mid
return mid;
}
}
return -1; //找不到便返回-1
}
};
● 时间复杂度:\(O(logn)\)
● 空间复杂度:\(O(1)\)
4.题目2:35.搜索插入位置
4.1.思路
元素插入的位置包括以下四种情况:
情况1:目标值与数组中某元素相同:nums = [1,3,5,6],target = 5,插入位置为2。
情况2:目标值插入数组某个位置:nums = [1,3,5,6],target = 2,插入位置为1。
情况3:目标值在所有元素之前:nums = [1,3,5,6],target = 0,插入位置为0。
情况4:目标值在所有元素之后:nums = [1,3,5,6],target = 7,插入位置为4。
4.2.解法1:暴力解法
查找数组中是否存在大于或等于目标值的元素,其位置相当于目标值应插入位置,若存在则返回当前元素位置。
若不存在,则表示所有数组元素的值都小于目标值,目标值应置于数组末尾。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
//情况1、2、3
for (int i = 0; i < nums.size(); i++) {
if (nums[i] >= target) return i;
}
return nums.size(); //情况4
}
};
● 时间复杂度:\(O(n)\)
● 空间复杂度:\(O(1)\)
4.3.解法2:二分查找[left, right]
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) { // [left, right]左闭右闭
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
// 分别处理如下四种情况
// 目标值在数组所有元素之前 -1 + 1
// 目标值等于数组中某一个元素 return mid;
// 目标值插入数组中的位置 [left, right],return right + 1
// 目标值在数组所有元素之后的情况 [left, right], 因为是右闭区间,所以 return right + 1
return right + 1;
}
};
● 时间复杂度:\(O(log n)\)
● 空间复杂度:\(O(1)\)
4.4.解法3:二分查找[left, right)
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) { // [left, right)左闭右开
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid;
}
// 分别处理如下四种情况
// 目标值在数组所有元素之前
// 目标值等于数组中某一个元素 return mid;
// 目标值插入数组中的位置 [left, right),return right
// 目标值在数组所有元素之后的情况 [left, right), 因为是右开区间,所以 return right
return right;
}
};
● 时间复杂度:\(O(log n)\)
● 空间复杂度:\(O(1)\)
5.题目3★:34. 在排序数组中查找元素的第一个和最后一个位置
5.1.思路
1.target 在数组范围的右边或者左边。
示例:nums = [3, 4, 5],target = 2 or target = 6,此时应该返回[-1, -1]。
2.target 在数组范围中,而数组中不存在target。
示例:nums = [3,6,7], target = 5,此时应该返回[-1, -1]。
3.target 在数组范围中,且数组中存在target。
示例:nums = [3,6,7], target为6,此时应该返回[1, 1]。
5.2.解法:二分查找[left, right)
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = searchLeftBorder(nums, target);
int rightBorder = searchRightBorder(nums, target);
if (leftBorder == -1 || rightBorder == -1) return {-1,-1};
else return {leftBorder, rightBorder};
}
private:
int searchLeftBorder(vector<int>& nums, int target) {
int leftBorder = -1;
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
}
else if (nums[mid] == target) {
leftBorder = mid;
right = mid;
}
else left = mid + 1;
}
return leftBorder;
}
int searchRightBorder(vector<int>& nums, int target) {
int rightBorder = -1;
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] == target) {
rightBorder = mid;
left = mid + 1;
}
else right = mid;
}
return rightBorder;
}
};
● 时间复杂度:\(O(logn)\),其中n为nums的长度。
● 空间复杂度:\(O(1)\)。
5.3.解法2:代码精简
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = searchBorder(nums, target, true);
int rightBorder = searchBorder(nums, target, false);
if (leftBorder == -1 || rightBorder == -1) return {-1,-1};
else return {leftBorder, rightBorder};
}
private:
int searchBorder(vector<int>& nums, int target, bool isLeft) {
int border = -1;
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
border = mid;
if (isLeft) right = mid;
else left = mid + 1;
}
}
return border;
}
};
● 时间复杂度:\(O(logn)\),其中n为nums的长度。
● 空间复杂度:\(O(1)\)。
6.题目4:69. x 的平方根
6.1.思路
6.2.解法1:二分查找[left, right]
class Solution {
public:
int mySqrt(int x) {
int left = 0, right = x;
while (left <= right) {
int mid = left + (right - left) / 2;
if ((long long)mid * mid == x) return mid;
else if ((long long)mid * mid < x) left = mid + 1;
else right = mid - 1;
}
return right;
}
};
● 时间复杂度:\(O(logx)\)。
● 空间复杂度:\(O(1)\)。
6.3.解法2:二分查找[left, right)
class Solution {
public:
int mySqrt(int x) {
if (x <= 1) return x;
int left = 0, right = x;
while (left < right) {
int mid = left + (right - left) / 2;
if ((long long) mid * mid < x) left = mid + 1;
else if ((long long) mid * mid > x) right = mid;
else return mid;
}
return left - 1;
}
};
● 时间复杂度:\(O(logx)\)。
● 空间复杂度:\(O(1)\)。
7.题目5:367.有效的完全平方数
7.1.思路
7.2.解法1:二分查找[left, right]
class Solution {
public:
bool isPerfectSquare(int num) {
int left = 1, right = num;
while (left <= right) {
int mid = left + (right - left) / 2;
if ((long long) mid * mid == num) return true;
else if ((long long) mid * mid < num) left = mid + 1;
else right = mid - 1;
}
return false;
}
};
● 时间复杂度:\(O(log num)\)。
● 空间复杂度:\(O(1)\)。
7.3.解法2:二分查找[left, right)
class Solution {
public:
bool isPerfectSquare(int num) {
if (num == 1) return true;
int left = 1, right = num;
while (left < right) {
int mid = left + (right - left) / 2;
if ((long long) mid * mid == num) return true;
else if ((long long) mid * mid < num) left = mid + 1;
else right = mid;
}
return false;
}
};
● 时间复杂度:\(O(log num)\)。
● 空间复杂度:\(O(1)\)。