34. 在排序数组中查找元素的第一个和最后一个位置【二分待完成】

题目来源

leetcode

题目描述

题目解析

前后双指针

第一反应前后双指针
但是题目中提出算法时间复杂度必须是 O(log n) 级别，就是指明了要用折半查找，然而既然想到了就写一下，巩固巩固，(*^_ *)

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if (nums == null){
            return res;
        }


        int low = 0;
        int high = nums.length -1;

        while (low < high){
            /*
             跳出循环的情况：
                没有目标： low = nums.length , high = nums.length - 1, 直接返回结果{-1, -1}
                有目标：   nums[low] == target, low = low
            * */
            while (low <= high && nums[low] != target){
                low++;
            }

            if (low == nums.length){
                return res;
            }

            res[0] = low;
            /*
            跳出循环的情况：while (low <= high && nums[high] != target)
                没有目标： 不可能，到了这一步，就至少有一个目标， 因此可以简写while (nums[high] != target)
                找到目标：
            * */
            while (nums[high] != target){
                high--;
            }
            res[1] = high;
        }

        return res;
    }

但是结果一定是超出时间限制
时间复杂度O(N)，空间复杂度O(1)

线性扫描

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if (nums == null){
            return res;
        }

        int left = -1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == target){
                left = i;
                break;
            }
        }

        if (left == -1){
            return res;
        }

        res[0] = left;

        // 此时left一定不为-1
        int right = left; // right 至少有一个值：left
        for (int j = nums.length - 1; j > left; j--){
            if (nums[j] == target){
                right = j;
                break;
            }
        }

        res[1] = right;


        return res;
    }

时间复杂度O(N)，空间复杂度O(1)

二分查找

如果遇到“有序”，“算法时间复杂度是 O(log n) 级别”之类的就要考虑二分法了