大佬教程收集整理的这篇文章主要介绍了二分查找总结，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
二分查找是一个非常基础的算法，它的原理很简单，但是写起代码来却很容易出错，尤其是在区间的范围定义时。最近刷《代码随想录》，对二分查找有了更加全面细致的理解，写一个自己的总结。在这里非常感谢《代码随想录》对我这个菜鸡的帮助。
二分查找的边界定义有两种，这里如果没有理解透彻的话，很容易写出错误的代码
要根据查找区间的定义来进行边界处理
边界定义的不同直接影响循环条件和 right 的更新
左闭右闭，即 [left, right] ，也就是 right 下标包含在我们要查找的数组中
此时循环条件为 while (left <= right) ，因为 left == right ，即 [left, left] 是有意义的
更新 right 时，right = mid - 1，因为 mid 所在下标已经查找过， 要查找 [left, mid - 1]的范围
左闭右开，即 [left, right)， right 下标不包含在我们要查找的数组中
此时循环条件为 while (left < right) ，因为left == right ，即 [left, left）是没有意义的
更新 right 时，right = mid，因为 要查找 [left, mid) 的范围， 这个范围不包括 mid 下标
更新 left 时 ，都是 left = mid + 1
我们看网上很多的代码计算 mid 时
不是 mid = （left + right）/ 2 ，
而是 mid = left + (right - left)/2
两者是等价的，但是前者当 left 和 right 数值都很大时，容易溢出，后者则不会
问题描述：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。
这是个二分查找的基本问题，给出两种写法，后面的题目默认只给出左闭右闭的写法
左闭右闭写法
class Solution {
public:
//左闭右闭写法
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; //左闭右闭区间
while (left <= right) { //条件是 <=
int mid = left + (right-left)/2; //防止溢出
if (nums[mid] == target) { //找到直接返回下标
return mid;
} else if (nums[mid] > target) { //此时更新区间为左边
right = mid - 1;
}
else { //此时更新区间为右边
left = mid + 1;
}
}
return -1; //没找到返回-1
}
};
左闭右开写法
class Solution {
public:
// 左闭右开写法
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size(); //区别1：左闭右开区间
while (left < right) { //区别2：判断条件
int mid = left + (right-left)/2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid; //区别3：right处理
}
else {
left = mid + 1;
}
}
return -1;
}
};
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2 示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
这道题目规定了不能使用指数函数和算符，我们想到通过遍历整数的平方，整数是有序的，可用二分查找
这道题目要写出没有问题的代码要注意这几点
class Solution {
public:
int mySqrt(int x) {
// left 一定需要是从 1 开始，原因是当输入是 x=1 时，计算出的mid=0,计算 x/mid 时会报错。
// 另外，当输入是 大于等于 1 时也不影响结果计算，当输入是 0 时，输出是 right(0) ，所以也是合理的。
int left = 1, right = x;
//左闭右闭区间
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid > x / mid) {
right = mid - 1;
}
else if (mid < x/mid) {
left = mid + 1;
}
else if (mid == x/mid) {
return mid;
}
}
// 没找到就返回最大的一个平法小于x的值
return right;
}
};
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
**
示例 1：
输入：num = 16 输出：true 示例 2：
输入：num = 14 输出：false
提示：
1 <= num <= 2^31 - 1
这题与上一题类似，只不过要判断余数是否为零
class Solution {
public:
bool isPerfectSquare(int x) {
int left = 1,right = x;
while (left <= right) {
int mid = left + (right - left)/2;
if (mid == x/mid) {
if (x % mid == 0) { //是否整除
return true;
}
return false;
} else if (mid > x/mid) {
right = mid - 1;
} else if (mid < x/mid) {
left = mid + 1;
}
}
return false;
}
};
问题描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
示例 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 = 7 输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0 输出: 0
示例 5:
输入: nums = [1], target = 0 输出: 0
这道题和上一题区别在于，如果没有找到返回插入位置，而不是返回-1。
没有找到最后要返回什么呢？我们考虑以下几种情况
所以返回left
class Solution {
public:
//左闭右闭区间
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right-left)/2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// 结束时 left = right + 1
return left;
}
};
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
提示：
0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递减数组 -109 <= target <= 109
通过二分查找先找到目标值，然后前后遍历，找到起始位置和结束位置，时间复杂度为nlog(n)
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int right = nums.size() - 1;
vector<int> res(2, -1); //初始化起始和结束位置，-1为没找到
int left = 0;
//左闭右闭区间
while (left <= right) {
int mid = left + (right - left)/2;
if (nums[mid] == target) {
int i = mid, j = mid;
while (i >= 0 && nums[i] == target) {//找到目标值之后，循环遍历寻找起始位置
i--;
}
while (j < nums.size() && nums[j] == target) {//循环遍历寻找结束位置
j++;
}
res[0] = i + 1;
res[1] = j - 1;
return res;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return res;
}
};
直接通过二分查找找到起始位置和结束位置，时间复杂度为log(n)
以上是大佬教程为你收集整理的二分查找总结全部内容，希望文章能够帮你解决二分查找总结所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。