二分搜索

应用：

应用查找顺序数据结构的目标值，如有序数组等。

原理：

1. 检索出数组索引的第一个和最后一个（left与right）
2. 得到mid，为left与right的一半
   • mid=（left+right）/2
   • mid=left+（right-left）/2，建议使用这个，当left与right过大时，相加第一个会溢出
3. 接下来用while循环（循环的条件是left<=right）找到目标值（假设数组从小到大排序），while循环中的条件是”>=“，跳出循环后left==right+1
   • 如果target大于nums[mid]，则说明target在mid右边，令left=mid+1
   • 如果target小于nums[mid]，则说明target在mid左边，令right=mid-1
   • 如果target等于nums[mid]，则说明target就在mid，返回mid
4. 最后返回left，即得到的数组元素的位置

代码实现：

class Solution{
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            //mid的取值
            int mid=left+(right-left)/2;
            if(nums[mid]>target)right=mid-1;
            else if(nums[mid]<target)left=mid+1;
            else return mid;
        }
        return left;
    }
}