当前位置: 首页 > news >正文

【算法——二分查找】

理论基础:

程序员面试经典题,二分搜索一个区间,区间查找 (LeetCode 34)_哔哩哔哩_bilibili

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili

这个是红蓝法,很牛:二分查找为什么总是写错?_哔哩哔哩_bilibili

在二分查找中,计算中间位置使用mid = left + (right - left) / 2而不是mid = (left + right) / 2主要是为了避免整数溢出的问题。

此类型题目多样总结:

34. 在排序数组中查找元素的第一个和最后一个位置

因为二分无法查到起止位置;所以用两次二分,一次左边界,一次右边界;

会不会漏查问题:比如left左边会不会还有target

#include<iostream>
using namespace std;
#include<vector>
int main()
{vector<int>nums = { 2,2 };int target = 3;int l = -1, r = nums.size();while (l + 1 != r)    //找第一个target{int m = l + (r - l) / 2;if (nums[m] < target) l = m;else r = m;}if (r >= nums.size() || nums[r] != target) return -1;cout << "l:" << l << "  r:" << r << endl;      //r就是第一个targetl = -1; r = nums.size();while (l + 1 != r)  //找最后一个target{int m = l + (r - l) / 2;if (nums[m] <= target) l = m;else r = m;}cout << "l:" << l << "  r:" << r << endl;      //l就是最后一个targetreturn 0;
}

35. 搜索插入位置

#include<iostream>
using namespace std;
#include<vector>
int main()
{vector<int>nums = { 1,3,5,6 };int l = -1, r = nums.size();int target = 7;while (l + 1 != r){int m = l + (r - l) / 2;if (nums[m] >= target) r = m;   //核心else l = m;}cout << r;return 0;
}

69. x 的平方根 

http://www.lryc.cn/news/446197.html

相关文章:

  • Cisco Packet Tracer的安装加汉化
  • MMain函数定义为WinMain函数看port1632.h和pwin32.h文件
  • 单词搜索问题(涉及递归等)
  • Redis的一些通用指令
  • C++中vector类的使用
  • cmaklist流程控制——调试及发布
  • 制作一个能对话能跳舞的otto机器人
  • git配置SSH
  • mozilla/pdf.js view.html加载指定页码
  • Qt之QFuture理解
  • 求二叉树的高度(递归和非递归)
  • Java查找算法——(四)分块查找(完整详解,附有代码+案例)
  • 进制数知识(2)—— 浮点数在内存中的存储 和 易混淆的二进制知识总结
  • 类似QQ聊天功能的Java程序
  • Redis 键值对数据库学习
  • 逆向推理+ChatGPT,让论文更具说服力
  • 「JavaScript深入」一文说明白JS的执行上下文与作用域
  • Qt C++设计模式->组合模式
  • Acwing Bellman-Ford SPFA
  • 我能禁止使用某协议的ip禁止访问我的资源吗
  • 快速理解TCP协议(二)——TCP协议中的拥塞控制机制详解
  • Linux:debug: systemtap: ubacktrace
  • 使用AI进行需求分析的案例研究
  • Python内置的re库
  • 毕业设计选题:基于ssm+vue+uniapp的面向企事业单位的项目申报小程序
  • jQuery 简介⑤属性操作
  • [Linux] Linux操作系统 进程的状态
  • 深入解析Python 中的 sortedcontainers 库:高效的排序数据结构
  • 什么是服务器日志,日志有什么作用?
  • Codeforces Round 971 (Div. 4)A-G1题解