LeetCode034-Find First and Last

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的位置
        // 不应该使用递减遍历，遇到整个数组由target构成的情况时间复杂度将会变为O(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: 二分查找时间复杂度
Space: 不需要使用额外的存储空间

Tips

二分查找，递归
简单的二分查找应用，需要注意的是，使用二分查找得到target的时候应该注意不要使用递增和递减查找最前和最后的target位置，应该继续使用二分查找法寻找最前最后的target位置，防止数组全部由target组成（如，target=1, nums=[1,1,1,1...,1,1,1]）的情况，时间复杂度下降为 。