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

2019/01/22 22:06 下午

问题

给定一个按照升序排列的整数数组 \(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]\)

解法

这个题乍一看就是二分查找的变种,考虑二分查找解决。
基本步骤如下:
使用二分法查找,假设\(start\)与\(end\)为数组起始位置与结束位置,有\(mid = (start + end)/2\)。此时,有三种情况会出现,我们首先排除掉\(nums[mid]!=target\)的两种情况:

  • 当\(nums[mid] < target\)时,\(start = mid + 1\);
  • 当\(nums[mid] > target\)时,\(end = mid - 1\);
    接下来,我们考虑当\(nums[mid] == target\)时的情况处理,此时,代表\(mid\)所在位置肯定是位于返回结果的中间,那么,起始位置要么就是\(mid\),要么肯定位于\(mid\)左侧,结束为止要么就是\(mid\),要没肯定位于\(mid\)右侧。
    继续使用二分法处理,但是与传统二分法不太一样的地方在于,各元素计算的方式有些不同,如果凭感觉写不出的话,可以在纸上写几个模拟数组试一下就行了。

代码

java 实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        int[] result = new int[]{-1,-1};
        
        while (start <= end) {
            //首先需要二分法查询到nums[mid]==target的情况
            int mid = (start + end)/2;
            if (nums[mid] == target) {
                int temp = mid;
                while (start<mid) {
                    int ml = (start+mid)/2;
                    if (nums[ml] < target) {
                        start = ml+1;
                    } else {
                        mid = ml; 
                    }
                }
                result[0] = start;
                mid = temp;
                while (mid < end) {
                    int mr = (end + mid)/2 + 1;
                    if (nums[mr] >target) {
                        end = mr -1;
                    } else {
                        mid = mr;
                    }
                }
                result[1] = end;
                return result;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            
        }
        return result;
    }
}