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

2020-05-11

LeetCode

二分查找

5 分钟读完 (大约 684 个字) 0次访问

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

题目：34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

方法一：二分查找

思路：通过二分查找缩小区间查找，找到等于target的数组元素后，根据该数组位置向两边寻找，直到找到不等于target的元素为止，从而确定目标值在数组中的开始位置和结束位置。

运行数据：执行用时：0 ms，内存消耗：43.2 MB

// LeetCode指定调用方法
public int[] searchRange(int[] nums, int target) {
		
    int len = nums.length;
    int l = 0;
    int r = len - 1;

    // 存储开始位置和结束位置
    int[] result = {-1,-1};

    // 二分查找
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > target) {
            r = mid - 1;
        } else if (nums[mid] < target) {
            l = mid + 1;
        } else { // 找到等于target的数组元素后，根据该数组位置向两边寻找，确定开始位置和结束位置
            for (int i = mid; i >= l; i--) {
                if (nums[i] != target) {
                    break;
                }
                result[0] = i;
            }
            for (int i = mid; i <= r; i++) {
                if (nums[i] != target) {
                    break;
                }
                result[1] = i;
            }
            break;
        }
    }

    return result;
}

方法二：二分查找（两次二分查找）

思路：通过两次二分查找分别查找左右边界，查找右边界时，通过searchBinaryBeforTarget()查target+1的位置，再减1得出右边界位置，由于target+1可能不在nums内，所以需要将searchBinaryBeforTarget()的范围扩展一位，以保证查target+1能找到对应位置。

运行数据：执行用时：0 ms，内存消耗：43.4 MB

// LeetCode指定调用方法
public int[] searchRange(int[] nums, int target) {
		
    // 通过两次二分查找分别查找左右边界
    int left = searchBinaryBeforTarget(nums, target);
    int right = searchBinaryBeforTarget(nums, target + 1) - 1;

    // 如果没有找到左右边界则返回[-1,-1],否则正常返回
    if (left == nums.length || nums[left] != target) {
        return new int[]{-1,-1};
    } else {
        return new int[]{left, right};
    }

}


// 二分查找
private int searchBinaryBeforTarget(int[] nums, int target) {

    int l = 0;
    int r = nums.length; // 右边界扩展一位

    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return l;
}