一、简介本文主要解释了二分法的左闭右闭区间，左闭右开区间两种写法，并且每个写法都举了相应的反例，范围写错的话可能会出现的错误等…
故事分享：
有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N - 1 本书。
保安怎么知道只有一本书没有登记出借，万一全部都没有登记呢？
这个故事其实说出了二分查找需要的条件
用于查找的内容逻辑上来说是需要有序的查找的数量只能是一个，而不是多个
比如在一个有序的数组并且无重复元素的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找。
在二分查找中，目标元素的查找区间的定义十分重要，不同的区间的定义写法不一样
因为查找的区间是不断迭代的，所以确定查找的范围十分重要，主要就是左右区间的开和闭的问题，开闭不一样，对应的迭代方式也不一样，有以下两种方式：
左闭右闭[left, right]
左闭右开[left, right)
二、主要步骤- 确定循环条件：
- 左闭右闭[left, right]( left = 0 ，right = size - 1 )：left <= right
- 左闭右开[left, right]( left = 0 ，right = size )：left < right确定区间中点： left + (right - left) / 2判断区间中点与寻找目标值的大小
- if(nums[middle] > target) right = middle - 1或者 right = middle
- else if (nums[middle] < target) left = middle + 1
- else return midlle
当区间中点不加入下次查找做法为左闭右闭的做法，反之则为左闭右开的做法。
三、二分法重点注意：left + (right - left) / 2 和 (left + right) / 2的结果相同，但如果left和right太大，直接相加会导致整形溢出，而改写成left + (right - left) / 2 则可以防止整形溢出
二分法最重要的两个点：
while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right迭代过程中 middle 和 right 的关系，到底是 right = middle - 1 还是 right = middle 三、整数二分 （一）例子
这是一个使用二分查找的例题
题目如下：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例一：
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例二：
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
出自704.二分查找 - 力扣(LeetCode)（leetcode-cn.com）
（二）.第一种做法 — 左闭右闭 1.写法循环条件要使用while(left <= right)，因为当(left == right)这种情况发生的时候，得到的结果是有意义的if(nums[middle] > target) ， right 要赋值为 middle - 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是[left, middle - 1]。
if(nums[middle] < target) ， left 要赋值为 middle + 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是[middle + 1, right]if(nums[middle] == target) 得出答案
2. C++ 代码
#include3.Java代码using namespace std; const int N = 1e6 + 10; int n, target; int nums[N]; int search(int nums[], int size, int target){ int left = 0, right = size - 1; while(left <= right) { int middle = left + (right - left) / 2; if(nums[middle] > target){ right = middle - 1; } else if(nums[middle] < target){ left = middle + 1; } else { return middle; } } return -1; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &nums[i]); scanf("%d", &target); int result = search(nums, n, target); printf("%d",result); }
import java.util.Scanner;
public class 二分查找 {
public static void main(String[] args) {
int nums[] = {-1, 0, 3, 5, 9, 12};
Scanner sc = new Scanner(System.in);
int target = sc.nextInt();
System.out.println(search(nums, target));
}
private static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (nums[middle] > target) {
right = middle - 1;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
}
4.图解
首先看一个数组，需要对这个数组进行操作。需要对33进行查找的操作，那么target 的值就是33。
首先，对 left 的值和 right 的值进行初始化，然后计算 middle 的值
left = 0, right = size - 1middle = left + (right - left) / 2
比较 nums[middle] 的值和 target 的值大小关系
if (nums[middle] > target)，代表middle向右所有的数字大于targetif (nums[middle] < target)，代表middle向左所有的数字小于target
既不大于也不小于就是找到了相等的值
nums[middle] = 13 < target = 33，left = middle + 1
见下图：
循环条件为 while (left <= right)
此时，left = 6 <= right = 11，则继续进行循环
当前，middle = left + (right - left) / 2，计算出 middle 的值
计算出 middle 的值后，比较 nums[middle] 和 target 的值，发现：
nums[middle] = 33 == target = 33，找到目标
（三）第二种做法 —— 左闭右开 1.写法第二种写法：每次查找的区间在 [left, right)，（左闭右开区间）， 根据区间的定义，条件控制应该如下：
循环条件使用while (left < right)if (nums[middle] > target)， right = middle，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。 2.C++版本
#include3.Java代码using namespace std; const int N = 1e6 + 10; int n, target; int nums[N]; int search(int nums[], int size, int target){ int left = 0, right = size; while(left < right) { int middle = left + (right - left) / 2; if(nums[middle] > target){ right = middle; } else if(nums[middle] < target){ left = middle + 1; } else { return middle; } } return -1; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &nums[i]); scanf("%d", &target); int result = search(nums, n, target); printf("%d",result); }
import java.util.Scanner;
public class 二分查找 {
public static void main(String[] args) {
int nums[] = {-1, 0, 3, 5, 9, 12};
Scanner sc = new Scanner(System.in);
int target = sc.nextInt();
System.out.println(search(nums, target));
}
private static int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int middle = left + (right - left) / 2;
if (nums[middle] > target) {
right = middle;
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
}
4.图解
需要查找的值为3
第一步是初始化 left 和 right 的值，然后计算 middle 的值
left = 0, right = size循环条件while (left < right)
因为是左闭右开区间，所以数组定义如下：
计算 middle 的值
比较 nums[middle] 和 target 的大小：因为 nums[middle] = 22 > target = 3所以 right = middle
符合循环的条件，接着计算 middle 的值
比较 nums[middle] 和 target 的大小：因为 nums[middle] = 9 > target = 3所以 right = middle
符合循环的条件，继续计算 middle 的值
比较 nums[middle] 和 target 的大小关系：因为nums[middle] = 0 < target = 3所以 left = middle + 1
符合循环条件，接着计算 middle 的值
比较 nums[middle] 和 target 的关系：nums[middle] = 3 == target = 3成功找到 target
四、浮点数二分
（一）例子当理解了整数二分之后，浮点数二分就变得极其简单。
（二）C++代码求x的开根号值
int main(){
double x ;
cin >> x ;
double l = 0 , r = x ;
// 1.精度判断
while( r - l > 1e-8 ){ // r-l 足够小时，可以认为相等，结束循环
double mid = (l + r) / 2;
if( mid * mid >= x ) r = mid ;
else l = mid ;
}
// // 2. 直接循环判断
// for( int i = 0; i < 100; i++ ){
// double mid = l + x >> 1 ;
// if( mid * mid >= x ) r = mid ;
// else l = mid ;
// }
printf("%.6lf", l) ; // 保留 x 位小数时，精度通常为 1e-(x+2)
return 0 ;
}
