数组：内存空间连续，数据类型统一，下标从0开始

二分查找

704

class Solution {
    public int search(int[] nums, int target) {
        // 方法一：暴力解法
        // for(int i = 0; i < nums.length; i++){
        //     if(nums[i] == target){//找到目标值
        //         return i;
        //     }
        // }
        // return -1;
        // 方法二：二分查找（元素有序且无重复元素），使用迭代，执行速度快，但是内存消耗大
        // return binarySearch(nums, target, 0, nums.length-1); 
        // 方法三：二分查找，统一使用左闭右闭区间
        // 上来先处理边界条件
        if(target < nums[0] || target > nums[nums.length - 1]){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;//右闭区间
        int mid = (left + right) >> 1;
        while(left <= right){//因为取得数组区间左右都是闭的，所以取等号的时候也能满足条件，还不需要退出循环
            if(target == nums[mid]){
                return mid;
            }else if(target < nums[mid]){
                right = mid -1;//往左区间缩
            }else{
                left = mid +1;
            }
            mid = (left + right) >> 1;
        }
        return -1;
    }
    // public int binarySearch(int[] nums, int target, int start, int end){
    //     int mid = (start+end)/2;
    //     int find = -1;
    //     if(start > end){//没有找到
    //         return -1;
    //     }
    //     if(target == nums[mid]){
    //         return mid;
    //     }else if(target < nums[mid]){
    //         find = binarySearch(nums, target, start, mid-1);
    //     }else{
    //         find = binarySearch(nums, target, mid+1, end);
    //     }
    //     return find;
    // }
}

搜索插入位置

35

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 有序数组，考虑用二分查找
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) >> 1;
        if(target < nums[left]){
            return left;
        }
        if(target > nums[right]){
            return right + 1;
        }
        while(left <= right){
            if(target == nums[mid]){
                return mid;
            }else if(target < nums[mid]){
                right = mid -1;
            }else{
                left = mid + 1;
            }
            mid = (left + right) >> 1;
        }
        return left;//找不到，返回需要插入的位置
    }
}

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

34

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 非递减说明是升序的，但可以有重复元素
        int[] arr = {-1, -1};
        if(nums.length == 0){
            return arr;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) >> 1;
        if(target < nums[left] || target > nums[right]){
            return arr;//边界值
        }
        int leftPoint;//目标数组的开始位置
        int rightPoint;//目标数组的结束位置
        while(left <= right){
            if(target == nums[mid]){
                leftPoint = mid;
                rightPoint = mid;
                while(leftPoint >= 0 && target == nums[leftPoint]){
                    arr[0] = leftPoint;
                    leftPoint--;//向左寻找重复元素
                }
                while(rightPoint <= (nums.length - 1) && target == nums[rightPoint]){
                    arr[1] = rightPoint;
                    rightPoint++;//向右寻找重复元素
                }
                return arr;//返回找到的目标值的位置
            }else if(target < nums[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
            mid = (left + right) >> 1;
        }
        return arr;//没有找到
    }
}

69、x的平方根

class Solution {
    public int mySqrt(int x) {
        // 使用二分查找
        int left = 0;
        int right = x;
        int mid = (left + right) / 2;
        while(left <= right){
            if((long)mid * mid < x){
                left = mid + 1;
            }else if((long)mid * mid > x){
                right = mid - 1;
            }else{
                return mid;
            }
            mid  = (left + right) / 2;
        }
        return right;
    }
}

367、有效的完全平方数

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

移除元素

27

class Solution {
    public int removeElement(int[] nums, int val) {
// 原地移除，所有元素
// 数组内元素可以乱序
        // 方法一：暴力解法，不推荐，时间复杂度O(n^2)
        // int right = nums.length;//目标数组长度，右指针
        // for(int i = 0; i < right; i++){
        //     if(val == nums[i]){
        //         right--;//找到目标数值，目标数长度减一，右指针左移
        //         for(int j = i; j < right; j++){
        //             nums[j] = nums[j + 1