网站用户推广,建网站公司用什么网站程序,课程网站开发流程图及原型图,上海松江招聘网最新招聘C刷题 – 二分查找 文章目录 C刷题 -- 二分查找一、原理二、例题1.二分查找2.使用二分查找确定target左右边界3.x的平方根 一、原理
条件#xff1a;数组为有序数组#xff0c;数组中无重复元素#xff0c;因为一旦有重复元素#xff0c;使用二分查找法返回的元素下标可能…C刷题 – 二分查找 文章目录 C刷题 -- 二分查找一、原理二、例题1.二分查找2.使用二分查找确定target左右边界3.x的平方根 一、原理
条件数组为有序数组数组中无重复元素因为一旦有重复元素使用二分查找法返回的元素下标可能不是唯一的
第一种写法
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size() - 1; // 定义target在左闭右闭的区间里[left, right]while (left right) { // 当leftright区间[left, right]依然有效所以用 int middle left ((right - left) / 2);// 防止溢出 等同于(left right)/2if (nums[middle] target) {right middle - 1; // target 在左区间所以[left, middle - 1]} else if (nums[middle] target) {left middle 1; // target 在右区间所以[middle 1, right]} else { // nums[middle] targetreturn middle; // 数组中找到目标值直接返回下标}}// 未找到目标值return -1;}
};第二种写法
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size(); // 定义target在左闭右开的区间里即[left, right)while (left right) { // 因为left right的时候在[left, right)是无效的空间所以使用 int middle left ((right - left) 1);if (nums[middle] target) {right middle; // target 在左区间在[left, middle)中} else if (nums[middle] target) {left middle 1; // target 在右区间在[middle 1, right)中} else { // nums[middle] targetreturn middle; // 数组中找到目标值直接返回下标}}// 未找到目标值return -1;}
};二、例题
1.二分查找
https://leetcode.cn/problems/binary-search/description/
2.使用二分查找确定target左右边界
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
该题目的要点在于非递减数组升序但是有可能有重复数字中寻找target的左右边界target可能有多个重复值的情况时间复杂度需要是O(log N)表明需要使用二分查找确定左右边界不能采用遍历方法确定边界先确定情况 target不再nums区间内target在nums区间内但是nums中没有targetnums中有target
使用二分查找确定边界的原理 二分查找在没有查找到target的时候target是在最终的(left, right)这个区间之内的可以使用这个原理来分别找出左右边界
确定右边界 当nums[mid]的值小于等于target的时候选择更新right_borderright_border需要跟着left更新因为无论是否找到target最终left一定会指向nums中大于target的数中最小的那个数就是target的有边界开区间左边界同理
特殊情况
nums为{2, 2}target为3最终左右边界输出值为(-2, 2)之间的差值大于1应该输出左右边界但是target却不在nums中 解决方案直接在最外面加一个判断target是否属于nums区间的条件
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint res;int tar_l leftBorder(nums, target);int tar_r rightBorder(nums, target);cout tar_l tar_r endl;if(nums.empty() || (target nums[0] || target nums[nums.size() - 1])){//target不在nums范围res.push_back(-1);res.push_back(-1);}else if(tar_r - tar_l 1){//target存在于nums中res.push_back(tar_l 1);res.push_back(tar_r - 1);}else{//target不存在于nums中res.push_back(-1);res.push_back(-1);}return res;}//寻找右边界 -- target右边的一个位置int rightBorder(vectorint nums, int target){int right_border -2;int left 0, right nums.size() - 1;//进行二分查找while(left right){int mid left ((right - left) / 2);if(nums[mid] target)//不断缩小右边界{right mid - 1;}else{//缩小左边界//且当找到target时left继续向右目的是找到最右边target的位置left mid 1;right_border left;//left最终指向的会是nums中大于target的最小数}} return right_border;}//寻找左边界int leftBorder(vectorint nums, int target){int left_border -2;int left 0, right nums.size() - 1;//进行二分查找while(left right){int mid left ((right - left) / 2);if(nums[mid] target)//不断缩小左边界{left mid 1;}else{//缩小右边界//且当找到target时right继续向右目的是找到最左边target的位置right mid - 1;left_border right;//right最终指向的会是nums中小于target的最大数}} return left_border;}};3.x的平方根
https://leetcode.cn/problems/sqrtx/submissions/483798269/
从题目的要求和示例我们可以看出这其实是一个查找整数的问题并且这个整数是有范围的。
如果这个整数的平方 恰好等于 输入整数那么我们就找到了这个整数如果这个整数的平方 严格大于 输入整数那么这个整数肯定不是我们要找的那个数如果这个整数的平方 严格小于 输入整数那么这个整数 可能 是我们要找的那个数重点理解这句话。
因此我们可以使用「二分查找」来查找这个整数不断缩小范围去猜。 方法一
猜的数平方以后大了就往小了猜猜的数平方以后恰恰好等于输入的数就找到了猜的数平方以后小了可能猜的数就是也可能不是。
class Solution {
public:int mySqrt(int x) {int min 0, max x;int res 0;while(min max){int mid min (max - min) / 2;if((long long)mid * mid x) // 防止乘法溢出{// 目标结果的平方小于等于x寻找出的就是范围内最大的满足平方x的数min mid 1;res mid;}else{max mid - 1;}}return res;}
};方法二
使用二分查找寻找边界目标数其实就是左边界
class Solution {
public:int mySqrt(int x) {int min 0, max x;int res 0;//寻找左边界while(min max){int mid min ((max - min) / 2);if((long long)mid * mid x){min mid 1;}else if((long long)mid * mid x){max mid - 1;res max;}else{return mid;}}return res;}
};
