LeetCode二分查找系列（704，34，35，69，367）

E 704.二分查找

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

根据看到的中间位置 mid 的值 nums[mid]，把待搜索区间分成三个部分：

• mid 位置左边的所有元素；
• mid 位置所在的元素；
• mid 位置右边的所有元素。
• 问题的答案只会在三个部分的其中一个部分，所以 while (left <= right) 里面有三个循环分支；
• 循环可以继续的条件是 left <= right，表示当 left 和 right 重合的时候，仍然继续查找。

public class Solution {
 
    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        // 在 [left..right] 区间里查找 target
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                // 下一轮搜索区间：[left..mid - 1]
                right = mid - 1;
            } else {
                // 此时 nums[mid] < target
                // 下一轮搜索区间：[mid + 1..right]
                left = mid + 1;
            }
        }
        // 走到这里，就可以判定输入数组里不存在目标元素，返回 -1
        return -1;
    }
}

LeetCode 34，35，69

把区间分成两个部分，去掉一定不存在目标元素的区间，只在有可能存在目标元素的区间里查找。这样当 left 与 right 重合的时候，我们才可以确定找到了目标元素（或者确定搜索区间里不存在目标元素）。

共同点：

如果当前猜的数 nums[mid] 符合某个性质，我们还不能确定它一定就是我们要找的元素，必须向左边（或者向右边）继续看下去，才能确定 nums[mid] 是不是我们要找的元素。 

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

一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

这里查找左右边界需明白，当找到nums[mid]等于target值时，左边界一定出现在mid的左边，右边界一定出现在mid的右边，所以可以区分寻找的区间范围，mid可能是左右边界，while（left < right)，左右相等时跳出，所以需要判断跳出时是否等于target，即是否存在目标值target，若[left，right]中存在结果值，则跳出后直接返回left，否则left的位置还需要进行一次判断。

1. 查找左边界

nums[mid] >=target，right = mid，区间是[left，mid]

nums[mid] < target，left = mid + 1，[mid+1，right]，没有等号一定取不到mid位置

2.查找右边界是

nums[mid] <=target，left = mid，区间是[mid， right]

nums[mid] > target，right = mid - 1，[left， mid - 1]，没有等号一定取不到mid位置

特别注意：

防止溢出，mid = left +（right - left）/  2，一般这种写法是取的是中间位置靠左的元素，

mid = left +（right - left + 1）/  2，取的是中间位置靠右的元素

同理，mid = （right + left）/  2 取到的是中间位置靠左的元素的位置，mid = （right + left + 1）/  2 取到的是中间位置靠右的元素的位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
 
        if(nums == null || nums.length == 0)//null和length的区别是否分配地址，前者无，后者有
            return new int[]{-1, -1};
 
        int firstIndex = findFirstIndex(nums, target);
        int lastIndex = findLastIndex(nums, target);
        if(firstIndex == -1)
            return new int[]{-1, -1};
        else
            return new int[]{firstIndex, lastIndex};        
    }
 
    public int findFirstIndex(int []nums, int target){
            int left = 0;
            int right = nums.length - 1;
            while(left < right){
                int mid = left + (right - left) / 2;
                if(nums[mid] < target)//[mid + 1, right]
                    left = mid + 1;
                else{//[left, mid],左边界一定在mid左边，即右边一定没有左边界，那相等target时，mid值有可能是左边界
                    right = mid;
                }
            }//left=right跳出
            if(nums[left] == target)//查找到则返回left，未查找到则返回-1；
                return left;
            return -1;
        }
 
        public int findLastIndex(int[] nums, int target){
            int left = 0;
            int right = nums.length - 1;
            while(left < right){
                int mid = left + (right - left + 1) / 2;
                if(nums[mid] > target)//[left, mid-1]
                    right = mid -1;
                else{//[mid, right],右边界一定在右边，即左边一定没有右边界，那相等target时，mid值有可能是右边界
                    left = mid;
                }
            }//left=right跳出
            if(nums[left] == target)//查找到则返回left，未查找到则返回-1；
                return left;
            return -1;
        }
}

E 35.搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

 题意是找到第一个大于等于target的位置，那把区间分成两部分，[left，mid]，[mid + 1，right]，最后left = right 时跳出循环，且在[left，right]间一定存在结果值，所以跳出后left位置无需再判断。

class Solution {
    public int searchInsert(int[] nums, int target) {
 
        int left = 0;
        int right = nums.length;//有可能为len
        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target)//[mid+1,right]
                left = mid + 1;
            else//[left,mid],
                right = mid; 
        }
        return left;//left = right,在[left,right]一定有结果
   }
}

E 69.搜索插入位置

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

提议是找到最后一个小于等于x的目标值，相当于找右边界，注意mid取中间靠右的数，那在mid位置的右边寻找，划分区间为[left，mid - 1]和[mid，right]，在[left，right]中一定存在结果值，无需在left位置处再判断。

class Solution {
    public int mySqrt(int x) {//寻找最后一个平方小于等于target的数，类似右边界
        if(x == 0){
            return 0;
        }
        int left = 1;
        int right = x - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if((long) mid * mid > x){/*[left, mid - 1],//需注意在较大数时，平方数可能会超int的范围[-2147483648, 2147483647],long的范围[-9223372036854774808,9223372036854774807],4字节和8字节，1字节是[-2^7,2^7-1]*/
                right = mid - 1;
            }
            else{//[mid, right]
                left = mid;
            }
        }
        return left;//left = right时，[left, right]中一定存在结果值所以无需再判断left位置的值
    }
}

E 69.有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如  sqrt 。

根据题意，搜索平方数等于num的值，类似经典二分查找

• mid 位置左边的所有元素；
• mid 位置所在的元素；
• mid 位置右边的所有元素。

class Solution {
    public boolean isPerfectSquare(int num) {
        if(num == 0 || num == 1)//注意1的取值情况
            return true;
        int left = 1;
        int right = num -1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if((long)mid * mid == num)
                return true;
            else if((long)mid * mid > num)//[left, mid - 1]
                right = mid - 1;
            else//[mid + 1, right]
                left = mid + 1;
        }
        return false;
    }
}