刷题笔记

34. Find First and Last Position of Element in Sorted Array

题目

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

思路

1. 二分法分别查找左侧起始坐标和右侧终止坐标。
2. 查找左侧起始坐标，采用夹并到一个元素的原则，并且当当前值大于等于目标值的时候，右侧-1缩小；小于的时候左侧+1缩小。因为最后加了一个判断，即当前值如果等于目标值，则讲index设置为当前值，这样不会导致缩小-1错过当前值。
3. 查找右侧起始坐标同理。

代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        ans[0] = findLeft(nums, target);
        ans[1] = findRight(nums, target);
        return ans;
    }   
        
    public int findLeft(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            }
            else left = mid + 1;
            if (nums[mid] == target) index = mid;
        }
        return index;
    }
    
    public int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            }
            else right = mid - 1;
            if (nums[mid] == target) index = mid;
        }
        return index;
    }
}

运行结果