代码随想录算法训练营第一天 | ( Part 1 ) 704. 二分查找
704. 二分查找
题目链接：https://leetcode.cn/problems/binary-search/
文档链接：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html (源于代码随想录)
可以参考视频讲解：https://www.bilibili.com/video/BV1fA4y1o715 (源于代码随想录)
思路：
处理对象 为 数组 ， 且 有序 ，
数组 可以 随机访问 ， 访问 某一确认位置 的 时间复杂度 为 O(1)
对于 有序 的 线性表 ，与 中间 的 值 进行 比较，一次 可以 排除掉 一半的数据 (/直接 找到 目标)
相对于在数组 中 一个一个 找 效率 有了 很大 的 提升
整体查找 的 时间复杂度 为 log(n)
易错点 和 需要注意的点：
-
target 和 mid点 在 写代码时 容易 下意识 搞混了
-
选择左侧区间时 注意 调整右边界 ， 选择右侧区间时 注意 调整左边界
-
注意 不要忘了 更新 mid 点 的值
实现时 的 思路：
-
使用 C++ STL标准库 中 的 begin() 、end()、获取 相对于 数据类型 的 逻辑 下标 ， 进而获取数组的长度
-
根据 比较 的 情况( 等于 / 小于 / 大于 ) ，提交 结果 下标 / 选择 左 右区间 ,
(如果 思考 相对 负载 太大 ， 可以 将 内容 划分 ， 先 从小块的内容 开始 思考/处理 ，逐渐 削弱 ,/ “蚕食” 问题 )
-
在 求 mid 值 时 ，注意 防溢出 ， “使用减法 配合 ，削减 中间结果 可能出现 的 最大值”
mid = left + ( right - left ) / 2 ;
-
“递归 逻辑” 运行 到 left 或 right 越过 对方 后
(实际上 是 非递归 实现)
-
当 left == right 时 ， 还有 最后 一个 元素 进行 比较 (在 虚拟渲染 运行 过程 时 可以 先从 一些 特殊/特征 点 思考 起 )
代码 实现：
int search(vector<int>& nums, int target) {
int len = end(nums) - begin(nums);
int left = 0;
int right = (len - 1);
int mid = left + (right - left)/2; //int mid = (left + right)/2;
while(left<=right){
if(target==nums[mid])
{
return mid;
}else
if(target<nums[mid]) //target 、 mums[mid] 在思考时 易 混晞
{
right = mid - 1; //注意 “选左区间 改 右边界 ，选右区间 改 左边界 ”
}else
if(target>nums[mid])
{
left = mid + 1;
}
mid = left + (right - left)/2; // 易漏
}
return -1;
}