二分查找（java）

写给我自己的：

最近又开始睡不着了，尤其是中午全宿舍都在呼呼大睡的时候，就我一个越睡越精神。。。我决定了，下次午觉再睡不着就起来刷力扣，等到困得不行了再睡，关于下午的课就随他吧，反正我也不听，什么时候困什么时候睡。

二分查找

可以使用「二分查找」的前提可以使用「二分查找」的前提是：问题告诉我们的单调性。有些问题虽然没有指出单调性，但是可以从题目中的描述得到可以逐步缩小搜索区间的条件，这些问题也可以使用「二分查找」来解决。

【leetcode704题】给定一个n个元素有序的(升序)整型数组nums 和一个目标值target，写一个函数搜索nums中的target,如果目标值存在返回下标，否则返回-1。

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        //长度为0时也是返回-1
        if(len == 0) return -1;
    
        while(left < right){
            int mid = (left + right) / 2;
            if(target == nums[mid]) return mid;
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return -1;//不存在
    }
}

【leetcode35题】给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

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

【leetcode69题】给你一个非负整数x,计算并返回x的算术平方根。由于返回类型是整数，结果只保留整数部分,小数部分将被舍去。注意:不允许使用任何内置指数函数和算符，例如pow(x, 0.5) 或者 x ** 0.5。

package Arraylist;

class Solution {
    public int mySqrt(int x) {
        int low = 0, high = x, res = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if ((long) mid * mid <= x) {
                low = mid + 1;
                res = mid;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }
}