Tag Archives: dichotomy

Leetcode 34 finds the first and last position of an element in the sorted array (medium)

given an ascending array of integers nums, and a target value target. Find the starting and ending positions in the array for the given target value.

your algorithm’s time complexity must be O(log n).

if there is no target value in the array, return [-1, -1].

example 1 :

enter : nums =,7,7,8,8,10 [5], target = 8
output: [3, 4]

sample 2 :

enter : nums =,7,7,8,8,10 [5], target = 6
output: [1, 1]

thought and code

O(log n) is the complexity of 

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int[] res = new int[] {-1, -1};

        if (nums.length < 1) return res;

        int firstIndex = search(nums, target - 1);
        
        // 如果大于target-1 的第一个索引就超级界 或者 第一个索引的值不是target 那么就说明当前数组没有目标值
        if (firstIndex == nums.length || nums[firstIndex] != target) return res;
        else res[0] = firstIndex;
		
        res[1] = search(nums, target) - 1;

        return res;    
    }

    public int search(int[] nums, int target) {
        // 找到大于target值的第一个位置
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (target >= nums[m]) l = m + 1;
            else r = m;
        }
        return l;
    }
}