Leetcode 34. First and last position of element in sorted array

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 234
Joined: Wed Oct 10, 2018 3:48 am

Leetcode 34. First and last position of element in sorted array

Post by dendiz » Mon Feb 04, 2019 11:56 pm

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:

Code: Select all

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

Code: Select all

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
If you see a sorted array think binary search. I'll use a modified binary search to find the indices. The idea is this:
If the middle element is target then there are a couple of options.

1. middle is zero which means the are no elements to the left, so this is the start index.
1a. middle == a.length - 1 which means there are no elements to the right so this is the end index.
2. a[middle - 1] == target which means we have to continue searching on the left or right
3. a[middle - 1] != target (could be greater or less) this means middle is either the start or end.

otherwise just go left or right depending on the the middle item being greater or smaller than the target.

Code: Select all

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[]{-1,-1};
        int start = bs(nums, target, 0, nums.length-1, true);
        int end = bs(nums, target, 0, nums.length-1, false);
        return new int[]{start, end}; 
    }
    int bs(int[] nums, int target, int start, int end, boolean s) {
        int mid = (start + end) / 2;
        if (start > end) return -1;
        
        if (nums[mid] == target) {
            if (s && mid == 0) return mid;
            if (!s && mid == nums.length - 1)return mid;
            if (s && nums[mid-1] < target) {
                return mid;
            }
            if (!s && nums[mid+1] > target) return mid;
            if (s) return bs(nums, target, start, mid-1, s);
            if (!s) return bs(nums, target, mid+1, end, s);
        }
        if (nums[mid] > target) {
            return bs(nums, target, start, mid-1, s);
        }
        if (nums[mid] < target) {
            return bs(nums, target, mid+1, end, s);
        }
        return -1;
        
    }
}

Post Reply