二分查找法

基本前提： 数组已经按照升序排列

基本原理：
首先将要查找的元素key和数组的中间元素mid比较
1.如果key 2.如果key=mid值，匹配成功，查找结束
3.如果key>mid值，只需要在数组后一半元素中继续查找

通过调节 left 和 right 就可以调整每一轮 sum 的长度。

例：假设要寻找元素5

初始low=0；high=数组的length-1

假设5< mid ，需要去数组前一半去查找，则high=mid-1，即搜索区间变为 [lo,mid-1] √
假设5> mid ，需要去数组后一半去查找，则low=mid+1，即搜索区间变为 [mid+1，high]

更新mid=2，值为8

更新mid=(0+1)/2=0, 值为2; 此时mid=lo

再比较，5>mid值；lo=mid+1=1;

更新mid=(1+1)/2=1; 此时 mid=5，搜索结束。

int bi(int[] nums,int val){
        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int mid=(left+right)/2;
            if(val == nums[mid]){ // 每一轮先判断
                System.out.println("bingo");
                return mid;
                
            }else if(val
                right=mid-1;
            }else if(val>nums[mid]){
                left=mid+1;
            }
        }
        return -1;
    }
}

注意：
二分查找不要出现else，而是把所有的情况用else if 写清楚

总结：
前提是给定有序单调递增的数组
取数组中间元素mid
由于一开始数组里面有n个元素，
折半一次还有n/2，折半k次之后是n/2^k
所以二分法复杂度时间是O(log n)