解题思路：对于查找相关的算法题，如果题目数组是有序的并且无重复元素，那么就可以使用二分查找法返回目标target元素的下标。有序和无重复元素是二分法的前提条件。

二分法的边界条件，这里我常用的方法就是左闭右闭。即，while(left <= right)，然后变动的区间边界不管是左边界还是右边界都统一减一操作，即left = mid + 1; right = mid – 1;

完整代码如下：

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

时间复杂度为O(log n)

35.搜索插入位置

这道题分析清楚target会出现在数组的哪些位置就可以解决了。

四种出现的位置：

1、目标值在数组所有元素之前

2、目标值在数组中找到了

3、目标值在数值中间但数组不包含这个目标值

4、目标值在数组所有元素之后

我通过实际举例子，四种情况都可以通过return right + 1;返回正确结果。其中情况2，在代码中是直接返回mid，其实mid就是right。

完整代码：

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

时间复杂度是O(log n)

34.在排序数组中查找元素的第一个和最后一个位置

解题思路：寻找target在数组里的左右边界，target会有三种情况

情况一：target在数组范围的左右两侧，例如数组{3, 4, 5}，target为2或6，此时应该返回{-1, -1}

情况二：target在数组范围中，且数组中不存在target，例如数组{2, 4, 5}，target为3，此时应该返回{-1, -1}

情况三：target在数组范围中，且数组中存在target，例如数组{3, 4, 5}，target为3，此时应该返回{0, 0}

分别使用两个二分查找寻找左边界和右边界。优先确定好，计算出来的左边界和右边界是不包含target值的

代码如下：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //两次二分法分别确定左右边界
        //开始分析三种情况
        int rB = searchRight(nums, target);
        int lB = searchLeft(nums, target);
        //情况一：target在数组两侧
        if(rB == -2 || lB == -2){
            return new int[]{-1, -1};
        }
        //情况三：target出现在了数组中
        if(rB - lB > 1){
            return new int[]{lB + 1, rB - 1};
        }
        //情况二：target大小属于nums数组内部，但是没有target的值
        return new int[]{-1, -1};
        
    }

    //事先规定，求出的左右边界是不包含target值的
    //先求右边界
    private int searchRight(int nums[], int target){
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(target < nums[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
                rightBorder = left;
            }
        }

        return rightBorder;
    }

    //求左边界
    private int searchLeft(int nums[], int target){
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(target > nums[mid]){
                left = mid + 1;
            }else{
                right = mid - 1;
                leftBorder = right;
            }
        }
        return leftBorder;
    }
}

时间复杂度为O(log n)

x的平方根

解题思路：target是x, nums数组是0~x，中间值为mid * mid，为了防止mid*mid溢出，要转成long类型

代码如下：

class Solution {
    public int mySqrt(int x) {
        //target是x, nums数组是0~x，中间值为mid * mid
        int left = 0;
        int right = x;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(x < (long)mid * mid){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return right;
    }
}

时间复杂度为O(log n)

367.有效的完全平方数

与69题x的平方根思路一样，target是传入的num，nums数组是0~num，中间值为mid*mid，为了防止mid*mid溢出，要转成long类型

代码如下：

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = num;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(num < (long)mid * mid){
                right = mid - 1;
            }else if(num > (long)mid * mid){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;
    }
}

时间复杂度为O(log n)