算法相关数据结构总结：
在排序数组中，二分法查找是一种高效率方法。
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。
二分法查找的思路如下：
- 首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
- 如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
- 如果某一步数组为空，则表示找不到目标元素。
二分法查找的时间复杂度O(logn)。
二分法查找
二分法查找的实现
非递归算法：
function binarySearch(arr,key){
var low=0; //数组最小索引值
var high=arr.length-1; //数组最大索引值
while(low<=high){
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key>arr[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
return -1; //low>high的情况，这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}
递归算法：
function binarySearch(arr,low,high,key){
if(low>high){return -1;}
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key<arr[mid]){
high=mid-1;
return binarySearch(arr,low,high,key);
}else{
low=mid+1;
return binarySearch(arr,low,high,key);
}
}
二分法查找的细节
从二分法的实现，我们可能觉得二分法查找很简单，但细节是魔鬼。
我们就是要深入细节，比如while循环中的不等号是否应该带等号，mid 是否应该加一等等。
二分查找的框架
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = (right + left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
声明一下，计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2，这个在很多算法题的解析中都已经注意写法了。
寻找一个数（基本的二分搜索）
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) { // 注意
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
为什么 while 循环的条件中是 <=，而不是 < ？
因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。
区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。
为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？
当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？
当然是去搜索 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。
注：
- 初始化right=nums.length-1,则while(left<=right),right=mid-1
- 初始化right=nums.length,则while(left<right),right=mid
力扣关于二分法查找的题
1）剑指offer53_Ⅰ：在排序数组中查找数字
题目：统计一个数字在排序数组中出现的次数。
解题思路：排序数组nums中的所有数字target形成一个窗口，窗口左右边界对应左右边首个元素。二分法查找左右边界，根据左边界判断等与target的个数。
算法代码：
class Solution {
public int search(int[] nums, int target) {
int l=0,r=nums.length-1;
int count=0;
while(l<=r){
int m = (l+r)/2;
if(nums[m]<target) l=m+1;
else r=m-1;
}
while(l<nums.length&&nums[l++]==target){
count++;
}
return count;
}
}
2）剑指offer53_Ⅱ。0~n-1中缺失的数字
题目：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
解题思路：递增有序的查找，就是考二分查找，比较nums[m]和m是否相等。
算法代码：
class Solution {
public int missingNumber(int[] nums) {
int i=0,j=nums.length-1;
while(i<=j){
int m=i+(j-i)/2;
if(nums[m]==m) i=m+1;
else j=m-1;
}
return i;
}
}