- 二分查找需要满足的条件：
- 用于查找的内容逻辑上来说是需要有序的
- 找的数量只能是一个，而不是多个
- 查找的区间
- 左闭右闭 [ left, right ]
- 左闭右开 [ left, right )
闭区间：是直线上介于固定两点间的所有点的集合（包括给定的两点），用 [a，b]来表示 (包含两个端点a和b）
开区间：指的是区间边界的两个值不包括在内
- 二分思想（查找过程）
前提条件：整个数组有序且是递增
-
首先选择数组中间的数字和需要查找的目标值比较（循环遍历数组）
-
如果不相等
- 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除（第一个if条件）
- 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除（第二个if条件）
-
当前两个if条件都不满足，说明中间数字等于目标值，就可以直接返回答案了（else）
- 确定中间的数字
- 无论区间长度是奇数还是偶数（奇数和偶数的定义概念 整数可以分成奇数和偶数两大类.能被2整除的数叫做偶数，不能被2整除的数叫做奇数。），中间数序号=左边界+（区间长度除2）即可（这边需要注意的是C++的‘ / ’运算符，结果只取整数部分）
- 需要注意的点
- while的循环条件：左边界与右边界应该满足什么关系
- 查找完一次后下一次的区间如何确定：即新左边界如何确定，新右边界如何确定
- 左闭右闭区间的二分查找 [ left, right ]
要查找的值为 x，中间的值序号为 m
*最开始的边界如何确定，左边界left=0，右边界right=数组大小size-1.
-
while 的循环条件：left <= right ,因为是两边都闭的区间，只有出现left==right的情况才能遍历整个数组，如果循环条件是left < right的话，会有一个数被忽视。
-
当中间值 m大于要查找的值 x时（第一个if条件），要确定下一个遍历区间，因为m大于x所以m向右的所有数字都大于x，全部排除，因为序号m的数字也与x比较并大于，所以也可以排除，则右边界取m相邻的左边数字序号，right=m-1，确定新的区间[ left, m-1 ]
-
当中间值 m小于要查找的值 x时（第二个if条件），要确定下一个遍历区间，因为m小于x所以m向左的所有数字都小于x，全部排除，因为序号m的数字也与x比较并小于，所以也可以排除，则左边界取m相邻的右边数字序号，left=m+1，确定新的区间[ m+1, right ]
举例的代码如下：
int search(int nums[], int size, int x) //nums是数组，size是数组的大小，target是需要查找的值
{
int left = 0;
int right = size - 1; // 定义了x在左闭右闭的区间内，[left, right]
while (left <= right) { //当left == right时，区间[left, right]仍然有效
int m = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
if (nums[m] > x) {
right = m - 1; //x在左区间，所以[left, m - 1]
} else if (nums[m] < x) {
left = m + 1; //x在右区间，所以[m + 1, right]
} else { //既不在左边，也不在右边，那就是找到答案了
return m;
}
}
//没有找到目标值
return -1;
}
总结
二分查找（Binary Search）是一种常用的查找算法，用于在有序数组中查找特定元素的位置。该算法通过将待查找区间不断缩小一半来进行查找，直至找到目标元素或确定目标元素不存在。
以下是二分查找的基本实现步骤：确定查找区间的起始位置和结束位置，通常初始时起始位置为数组的第一个元素的索引，结束位置为数组的最后一个元素的索引，计算中间元素的索引，可以使用 (起始位置 + 结束位置) / 2 的方式计算。比较中间元素与目标元素的大小关系：如果中间元素等于目标元素，则找到目标元素，返回中间元素的索引。如果中间元素大于目标元素，则目标元素可能位于左半部分，更新结束位置为中间元素的前一个位置。如果中间元素小于目标元素，则目标元素可能位于右半部分，更新起始位置为中间元素的后一个位置。如果起始位置小于等于结束位置，则重复步骤 2 和步骤 3，直至起始位置大于结束位置。如果起始位置大于结束位置，表示目标元素不存在于数组中，返回一个特定的标识（如 -1）表示未找到。
二分查找的关键点在于每次都将查找区间缩小一半，因此它的时间复杂度为 O(log n)，其中 n 是数组的大小。这使得二分查找成为一种高效的查找算法。
标签：二分,right,元素,中间,查找,区间,left From： https://www.cnblogs.com/ywx1207/p/17840228.html