您现在的位置是：首页 >学无止境 >代码随想录第一天|二分查找和双指针网站首页学无止境

Leetcode 704 二分查找

题目链接: 704
自己的思路: 由于是有序数组，所以首先想到使用二分查找，通过取左右两边的中点依次判断与目标值的大小，逐渐缩小判断区间。分左闭右开和左闭右闭两种。
正确思路: 二分查找
左闭右闭

代码:

class Solution {
    public int search(int[] nums, int target) {
        //初始化左右指针为两个端点
        int left = 0;
        int right = nums.length - 1;
        //左闭右闭，right可以取到右边
        while(left <= right){
            //防止数值溢出
            int middle = left + (right-left)/2;
            //左半区间没有目标值（包括middle）
            if (nums[middle]<target) left = middle + 1;
            //右半区间没有目标值（包括middle）
            else if (nums[middle]>target) right = middle - 1;
            //找到目标值
            else return middle;
        }
        //整个数组没有目标值
        return -1;
    }
}

左闭右开
代码:

class Solution {
    public int search(int[] nums, int target) {
        //初始化左右指针为两个端点
        int left = 0;
        int right = nums.length;
        //左闭右开，right取不到右边
        while(left < right){
            //防止数值溢出
            int middle = left + (right-left)/2;
            //左半区间没有目标值（包括middle）
            if (nums[middle]<target) left = middle + 1;
            //右半区间没有目标值（包括middle） 由于right取不到右边，所以设置right为middle
            else if (nums[middle]>target) right = middle;
            //找到目标值
            else return middle;
        }
        //整个数组没有目标值
        return -1;
    }
}

复杂度分析：
时间复杂度：$\mathcal{O}(\log (n))$ $n$为数组的长度
空间复杂度：$\mathcal{O}(1)$

相似题型

Leetcode 35 搜索插入位置

题目链接: 35
自己的思路: 由于是有序数组，所以首先想到使用二分查找，如果找到元素，返回它的索引，如果找不到元素，则找第一个大于target的元素，插在其左边即可。如果在数组中找不到元素的话，那么最终right和left落的位置一定是，left在第一个大于该元素的位置，right在left左边一个位置，所以最终返回left即可
正确思路: 二分查找
左闭右闭

代码:

class Solution {
    public int searchInsert(int[] nums, int target) {
        //定义左右两个指针
        int left = 0;
        int right = nums.length - 1;
        //左闭右闭
        while(left<=right){
            //取中点，防止溢出
            int middle = left + (right - left)/2;
            //右边没有，在左边找
            if (nums[middle] > target) right = middle - 1;
            //左边没有，在右边找
            else if (nums[middle] < target) left = middle + 1;
            //如果在数组中找到元素，返回索引即可
            else return middle;
        }
        //如果找不到元素即返回第一个大于target的索引
        return left;
    }
}

复杂度分析：
时间复杂度：$\mathcal{O}(\log (n))$ $n$表示数组的长度
空间复杂度：$\mathcal{O}(1)$

Leetcode 27 移除元素

题目链接: 27

自己的思路:双指针经典问题，可以定义一个快指针，一个慢指针，快指针在前面判断数组中的值是否等于val，如果不等于则把快指针的值赋给慢指针的位置，然后快慢指针都向前进一步；如果等于，快指针往前进一步，慢指针不动，这样前slow个元素就是移除val以后的数组了，也就是我们想要的。
正确思路:双指针

双指针解法
代码:

class Solution {
    public int removeElement(int[] nums, int val) {
        //定义慢指针
        int slow = 0;
        //快指针遍历，无论fast处的值等不等于val，快指针都前进一步
        for (int fast=0;fast<nums.length;fast++){
            //快指针的值如果不等于val，则将此处的值赋给慢指针位置，慢指针前进一步
            if (nums[fast]!=val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        //因为最后慢指针++了，所以返回前slow个元素即可
        return slow;
    }
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$

相似题型

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

题目链接: 26

自己的思路:双指针经典问题，可以定义一个快指针，一个慢指针，快指针在前面判断数组中的值是否等于之前慢指针的值，如果不等于则把快指针的值赋给慢指针的位置，然后快慢指针都向前进一步；如果等于，快指针往前进一步，慢指针不动，这样前slow个元素就是移除val以后的数组了，也就是我们想要的。
正确思路:双指针

双指针解法
代码:

class Solution {
    public int removeDuplicates(int[] nums) {
        //定义慢指针，由于要判断慢指针前面一个位置的值作为临时变量，所以慢指针必须从1开始
        int slow = 1;
        //快指针也必须从1开始，无论如何快指针都前进一步
        for (int fast=1;fast<nums.length;fast++){
            //定义临时变量用来记录慢指针前面一个位置的值
            int temp = nums[slow-1];
            //如果快指针不等于之前慢指针的值，则把快指针的值赋给慢指针的位置，慢指针前进一步
            if (nums[fast]!=temp){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        //由于最后slow++，所以直接返回slow即可，slow即为新数组的长度
        return slow;
    }
}

复杂度分析：
时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$