1. 基本介绍
二分思想一般用于查找，见其名知其意，这是一个半半开的算法。第一次接触二分思想的时候是高中的数学学习中，给定一个方程 f(x) = 0的根所在的区间，可以用根存在定理不断二分区间，当区间长度小于给定的精度时，即可近似求出方程的解，当然也可以用来求平方根和立方根等。同样，这种查找思想也可以运用于计算机内结构化数据的查找。（tips: 二分查找思想简单，细节魔鬼）。(详讲博客推荐)
二分查找有很多应用，由于其时间复杂度很低，它可以暴力破解很大的数据。
- 核心思想
使用二分查找的前提：待查找序列必须有序（升序或降序，本文主要以升序为例）
确定查找区间(left, right)，取区间中间值mid = (left + right)/2，比较中间值与左右两边的值，确定待查元素key所在区间，舍弃无效区间(mid = left 或mid = right)。
思路很简单，细节是魔鬼。
一：二分法算法分析
1、二分查找算法定义
二分查找又称折半查找，它是一种效率较高的查找方法。
二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。
2、基本思想
（1）首先确定该区间的中点位置
（2）将待查的K值与R[mid]比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找
（3） ① 若R[mid].key>K，将查找区间变为**[left,mid-1]**
②若R[mid].key<K，将查找区间变为**[mid+1,right]**
3、优缺点
③ 二分查找的优点
折半查找的时间复杂度为O(logn)，远远好于顺序查找的O(n)。
④ 二分查找的缺点
虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
4、二分查找常用场景
寻找一个数、寻找左侧边界、寻找右侧边界。
细节：
while循环中的不等号是否应该带等号，mid 是否应该加一等等。
5、二分查找常用框架
1 int binarySearch(int[] nums, int target) {
2 int left = 0, right = ...;
3
4 while(...) {
5 int mid = left + (right - left) / 2;
6 if (nums[mid] == target) {
7 ...
8 } else if (nums[mid] < target) {
9 left = ...
10 } else if (nums[mid] > target) {
11 right = ...
12 }
13 }
14 return ...;
15 }
分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节
计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2
————————————————
版权声明：本文为CSDN博主「噜啦啦412」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_57229058/article/details/123763083
标签：二分,...,right,--,mid,算法,查找,left From： https://www.cnblogs.com/Gaowaly/p/17001556.html