Find First and Last Position of Element in Sorted Array

Question:

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

Your algorithm's runtime complexity must be in the order of O(log n).

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

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

解法代碼

public class LeetCode34 {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[] { -1, -1 };
        }
        int index = search(nums, target, 0, nums.length - 1);
        if (index == -1) {
            return new int[] { -1, -1 };
        }
        int before = index;
        int after = index;

        // 同樣使用二分查找找到最靠前的target的位置
        // 不應(yīng)該使用遞減遍歷，遇到整個數(shù)組由target構(gòu)成的情況時間復(fù)雜度將會變?yōu)镺(n)
        while (before > 0 && nums[before - 1] == target) {
            before -= 1;
            before = search(nums, target, 0, before);
        }

        while (after < nums.length - 1 && nums[after + 1] == target) {
            after += 1;
            after = search(nums, target, after, nums.length - 1);
        }

        return new int[] { before, after };
    }

    public int search(int[] nums, int target, int start, int end) {
        if (end < start) {
            return -1;
        }
        // 防止溢出
        int mid = start + (end - start) / 2;

        if (nums[mid] > target) {
            return search(nums, target, start, mid - 1);
        } else if (nums[mid] < target) {
            return search(nums, target, mid + 1, end);
        } else {
            return mid;
        }
    }
}

測試用例

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.Collection;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

import com.kay.pro.alog.LeetCode34;

@RunWith(Parameterized.class)
public class LeetCode34Test {
    private LeetCode34 leetCode;
    private int[] nums;
    private int target;
    private int[] ret;
    
    public LeetCode34Test(int[] nums, int target, int[] ret) {
        this.nums = nums;
        this.target = target;
        this.ret = ret;
    }
    
    @Before
    public void before() {
        leetCode = new LeetCode34();
    }
    
    @Parameters
    public static Collection<?> reverserArrays() {
        return Arrays.asList(new Object[][]{
            {new int[]{5, 7, 7, 8, 8, 10}, 8, new int[]{3, 4}},
            {new int[]{5, 7, 7, 8, 8, 10}, 6, new int[]{-1, -1}},
            {new int[]{1, 1, 1, 1, 1, 1}, 1, new int[]{0, 5}},
            {new int[]{}, 1, new int[]{-1, -1}}
        });
    }
    
    @Test
    public void leetCode33() {
        assertArrayEquals(ret, leetCode.searchRange(nums, target));
    }
}

Output：

Time And Space Complexity

Time: 二分查找時間復(fù)雜度
Space: 不需要使用額外的存儲空間

Tips

二分查找，遞歸
簡單的二分查找應(yīng)用，需要注意的是，使用二分查找得到target的時候應(yīng)該注意不要使用遞增和遞減查找最前和最后的target位置，應(yīng)該繼續(xù)使用二分查找法尋找最前最后的target位置，防止數(shù)組全部由target組成（如，target=1, nums=[1,1,1,1...,1,1,1]）的情況，時間復(fù)雜度下降為 。