您现在的位置是：首页 >技术教程 >代码随想录算法训练营第一天|704. 二分查找、35.搜索插入位置、34. 在排序数组中查找元素的第一个和最后一个位置 27.移除元素网站首页技术教程

LeetCode 704. 二分查找

思路：基本的二分查找方法。
关键点：在while循环中的L<R(L<=R)中间的符号，取决于区间的左闭右开、左闭右闭。（当然题目变化的话也可能和具体题目相关。）

所谓的：
左闭右闭：就是R=size-1；R指向最后一个元素；
左闭右开：就是R= size； R指向最后一个元素的下一个。
之后的循环中保持这个规律即可。

左闭右闭

class Solution {
    public int search(int[] nums, int target) {
    	// 左闭右闭
        int size = nums.length;
        int L = 0;
        int R = size - 1;
        while(R>=L){
            int mid = L + ((R-L)>>1);
            if(nums[mid]>target){
                R = mid - 1;
            }
            else if(nums[mid] < target){
                L = mid + 1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

左闭右闭

class Solution {
    public int search(int[] nums, int target) {
        // 左闭右开
        // whlie(L<R)  此时L==R 没有含义 因为左闭右开 的情况不会出现相等
        int size = nums.length;
        int L = 0;
        int R = size;
        while(L<R){
            int mid = L + ((R - L)>>1);
            if(nums[mid] > target){
                R = mid;
            }
            else if(nums[mid] < target){
                L = mid + 1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

LeetCode：35:搜索插入位置

思路：题目要求的复杂度是logn。想到二分查找
关键点：二分查找中选择使用左闭右开的方法，这样可以避免另外加一个变量来记录target不在nums的情况。

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 左闭右开
        int size = nums.length;
        int L = 0;
        int R = size;
        while(L<R){
            int mid = L + ((R-L)>>1);
            if(nums[mid] > target){
                R = mid;
            }
            else if(nums[mid] < target){
                L = mid + 1;
            }
            else{
                return mid;
            }
        }
        return R;
    }
}

LeetCode：34：在排序数组中查找元素的第一个和最后一个位置(需要二刷)。

思路：思路很简单，两步二分查找，找到左边第一个大于等于target和右边第一个大于target的数。细节很繁琐。

关键点：再次理解符号的用法。>= 这些符号体现了不同的用法。这里的关键就是找到左边第一个大于某一个数的情况。用的也是左闭右闭。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 基本思想能够想到，但是具体的细节有很多要考虑
        // 这一题，再次认识里面的符号的作用>=

        int left = binarySearch(nums, target); // 寻找左边第一个大于>=target的数，全是大于则没有，有了等于就是第一个。
        int right = binarySearch(nums, target+1)-1; // 寻找右边第一个大于target的数
        if(left<=right && right<nums.length && nums[left]==target && nums[right]==target){
            return new int[] {left, right};
        }
        return new int[] {-1, -1};
    }

    public int binarySearch(int[] nums, int target){
        int L = 0;
        int R = nums.length - 1;
        while(L<=R){
            int mid = L + ((R-L)>>1);
            if(nums[mid] < target){
                L = mid+1;
            }
            else if(nums[mid] >= target){  // 注意这里的变化，要的是>= 这样会接着执行指导左边第一个target，或者是左边第一个大于target的数。
                R = mid-1;
            } 
        }
        return L;
    }
}

LeetCode：27.移除元素

思路：被题目迷惑了。’这道题目不单单返回最后的长度，还要将里面对应的val删除。

• 暴力。两层for，遍历找到val，然后将后面的元素依次向前移动一位。
• 双指针：fast找到val，slow记录新数组的最后一位。

注意：还要删除里面的对应值为val的元素。

解法一：暴力

class Solution {
    public int removeElement(int[] nums, int val) {
        // 半天没读懂题目，明确说返回新数组的长度就好了。
        // 先来一个暴力解法：
        // 两层for循环，找到对应的val之后就将后面的元素整体往前移一位，
        // 同时,i--;size-- 因为整体都少了一个
        // 最后返回size。
        int size = nums.length;
        for(int i=0;i<size;i++){
            if(nums[i] == val){
                for(int j = i+1;j<size;j++){
                    nums[j-1] =nums[j]; 
                }
                i--;
                size--;
            }
        }
        return size;
    }
}

解法二：双指针(看了代码随想录)

class Solution {
    public int removeElement(int[] nums, int val) {
        // 单单返回最后的长度还不行，还要将里面的元素删除。
        // 双指针解法；快慢指针
        // 画图就好理解了。
        int size= nums.length;
        int slow = 0;
        for(int fast=0;fast<size;fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast]; 
                slow++;
            }
        }
        return slow;
    }
}