二分查找：二分查找算法也称折半搜索算法，对数搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
具体找的方式：
1. 找到数组的中间位置。
2. 检测中间位置的数据是否与要查找的数据key相等。
a: 相等，找到，打印下标，跳出循环。
b: key < arr[mid], 则 key 可能在 arr[mid] 的左半侧，继续到左半侧进行二分查找。
c: key > arr[mid], 则 key可能在 arr[mid] 的右半侧，继续到右半侧进行二分查找。
如果找到，则返回下标，否则继续，直到区间中没有元素时，说明 key 不在集合中，这时打印找不到。
易错点：
1. right 的右半侧区间取值，该值决定了后序的写法。
循环条件写 left <= right 和 left < right 的区别是什么？其它地方需要进行哪些改动？
（1）区别在于是否包含最右边的边界值，因为当 left==right 时，不会再进入循环体，所以right 初始化时就取值为数组的长度（sizeof(arr)/sizeof(arr[0])），这样在 for 循环中就能保证是在这样一个左闭右开的区间[left,right)，且 right 赋值应该为 right = mid 而非 right = mid-1，因为右半边是开区间，取 mid-1 就无法验证到 mid-1 是否是目标值。
如果对二分查找不熟练，建议使用 left <= right，然后再根据题目去改变目标查找条件。
2. while 循环的条件是否有等号。
3. 求中间位置的方法，mid = (left + right) / 2 容易造成溢出。原因：left 可能不断增大，如果到极限状态，也就是 left 达到了 right-1 的时候刚好数组的长度又很大，那么就可能导致 left + right 的溢出出现负数的情况。
改进写法：
（1）>>是右移运算符，右移一位相当于除2，右移 n 位相当于除以 2 的 n 次方。
mid=(left+right)>>1 等价于 mid=(left+right)/2。
（2）left+(right-left)/2 进行通分等同于 (left + right) / 2。
4. 更改 left 和 right 的边界时，不确定是否要 +1 和 -1。
查找过程举例：
nums[mid] < target，因此 target 是在 mid 的右边区域，让 left=mid+1，在 mid 右半边区域查找。
当满足条件 nums[mid] == target 时就可以退出循环，两次就找到了这个数，时间复杂度为 O(logn)。
参考代码：
//方法一，采用[left, right] 区间 - 左闭右开 #include <stdio.h> int main() { int arr[] = {1,2,3,4,5,6,7,8,9,10}; printf("输入要查找的数字："); int key = 0; scanf("%d", &key); int left = 0; int right = sz-1;//right位置的数据可以取到 while(left<=right)//right位置有数据，必须要添加=号 { int mid = (left+right)/2;//如果left 和 right 都是最⼤ int，这么操作就越界了，可参考方法二中的写法 if(arr[mid]>key)//key<中间位置数据，说明key可能在左半侧，需要改变右边界 { right = mid-1;//right位置的数据可以取到，因此right=mid-1 } else if(arr[mid]<key)// key>中间位置数据，说明key可能在右半侧，需要改变左边界 { left = mid+1;//left位置的数据可以取到，因此left=mid+1 } else { printf("找到了，下标是：%d\n", mid); break; } } if(left>right) printf("找不到\n"); return 0; }
// 方法二，采用[left, right) 区间 - 左闭右闭 #include <stdio.h> int main() { int arr[] = {1,2,3,4,5,6,7,8,9,10}; printf("输入要查找的数字："); int key = 0; scanf("%d", &key); int left = 0; int right = sizeof(arr)/sizeof(arr[0]); //right位置的数据取不到 while(left<right) //right位置没有数据，此处不需要添加= { int mid = left+(right-left)/2;//相当于是如果数组⻓度为偶数，中间位置有两个元素，取靠左边的 if(arr[mid]>key) // key<中间位置数据，说明key可能在左半侧，需要改变右边界 { right = mid; //right位置的数据取不到，因此right=mid，不需要减1 } else if(arr[mid]<key)//key>中间位置数据，说明key可能在右半侧，需要改变左边界 { left = mid+1; //left位置的数据可以取到，因此left=mid+1 } else { printf("找到了，下标是：%d\n", mid); break; } } if(left>=right) printf("找不到\n"); return 0; }
