代码随想录day1 Java版本

学习内容为二分查找和双指针

二分查找

力扣704

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

注意点：区间

对于左闭右闭区间，也就是[left, right]

        1.while (left <= right) 要使用 <= ，因为left == right是有意义的

        2.目标值在mid左侧时，right = mid-1而不是mid

对于左闭右开区间，也就是[left, right）

        1.while (left < right) 要使用 < ，因为left == right没有意义

        2.目标值在mid左侧时，right = mid而不是mid - 1，因为下一个区间不会比较right处的值

双指针

力扣27 移除元素

给定一个数组和目标值val，要求原地移除数组中所有值等于val的元素，返回数组长度。

class Solution {
    public int removeElement(int[] nums, int val) {
        int j = nums.length;
        int i = 0;
        while(i < j){
            if(nums[i] == val){
                nums[i] = nums[j - 1];
                j --;
            }else{
                i ++;
            }
        }
        return i;
    }
}

 双指针即通过一快一慢两个指针来减少暴力算法的时间复杂度。

相关练习 二分法部分

力扣35 搜索插入位置

关于此题，要插入的位置就是首个大于target的下标。我们使用左闭右闭区间，当最后跳出循环的时候，一定是left大于right，那么上一步就一定会是left == right。如果 （此刻left == right）

（1）因为right - 1导致left > right， 则说明nums[right]是大于target的，所以此刻的right（跳出循环后的right + 1）（也就是left）就是要插入的位置。

（2）因为left + 1导致left > right，说明nums[left]（nums[right]）是小于target的，所以left + 1后的下标，也就是新的left的下标是要插入的位置

综上，当最后跳出循环后，要插入的位置为left

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

力扣34 查找元素第一个位置和最后一个位置

思路就是两次二分查找分别找到第一个位置和最后一个位置。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0){
            return new int[]{-1, -1};
        }
        int first = findFirstPosition(nums, target);
        if(first == -1){
            return new int[]{-1, -1};
        }
        int last = findLastPosition(nums, target);
        return new int[]{first, last};
    }
    private int findFirstPosition(int[] nums, int target){
        int i = 0;
        int j = nums.length - 1;
        while(i < j){
            int mid = (i + j) >>> 1;
            if(nums[mid] < target){
                // 我们要在[mid+1,j]中继续二分查找
                i = mid + 1;
            }
            else if(nums[mid] == target){
                // 我们要在[i,mid]继续查找
                j = mid;
            }
            else{
                // 我们要在[i,mid-1]继续查找
                j = mid - 1;
            }
        }
        if(nums[i] == target){
            return i;
        }
        return -1;
    }
    private int findLastPosition(int[] nums, int target){
        int i = 0;
        int j = nums.length - 1;
        while(i < j){
            int mid = (i + j + 1) >>> 1;
            if(nums[mid] < target){
                // 我们要在[mid+1,j]查找
                i = mid + 1;
            }
            else if(nums[mid] == target){
                // 我们要在[mid,j]继续寻找
                i = mid;
            }
            else{
                // 我们要在[i,mid-1]继续寻找
                j = mid - 1;
            }
        }
        return i;
    }
}

本题也可以使用左闭右闭区间的做法，用一个变量单独记录最左或者最右位置

力扣69 x的平方根

class Solution {
    public int mySqrt(int x) {
        long i = 0;
        long j = x;
        while (i <= j) {
            long mid = (i + j) >>> 1;
            if (mid * mid > x) j = mid - 1;
            else if (mid * mid == x)return (int)mid;
            else i = mid + 1;
        }
        return (int)j;
    }
}

还是找边界，即可以找mid*mid大于x的左边界（首个大于x的mid*mid，那么mid-1就是我们要找的结果），也可以是mid*mid<x的右边界（最后一个小于x的mid*mid，mid就是我们要找的结果），类似力扣35证明过程，可以证明，i-1或者j就是最后我们要的结果。 

力扣367 有效的完全平方数

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

相关练习 双指针部分

 26 删除有序数组中的重复项

 与例题双指针类似。相同方向双指针，i在前，j在后指向下一类数字，当j找到位置后，令i+1并赋值，直到j到头为止（这里j可以一位一位地加而不是内圈的while循环，就不需要break跳出了）

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int j = 0;
        while (j < nums.length) {
            while (j < nums.length && nums[i] == nums[j]) {
                j ++;
            }
            if (j >= nums.length) break;
            i ++;
            nums[i] = nums[j];
        }
        return i + 1;
    }
}