IT博客汇 | 34. Find First and Last Position of Element in Sorted Array

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

10k发表于 2023-07-09 00:00:00

Question

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

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

You must write an algorithm with O(log n) runtime complexity.

Algorithm

For this problem, I firstly came up a trivial binary search, when we encounter the target, we use a while loop to find the left and right side, however this is O(n) in worst case.

The standard solution is to use two separate binary search. Actually I came up this idea at first to keep the O(Log(n)) time, but I tried to put the left and right side handle in one loop which is impossible. So I quit. Actually we can separated them they it can be implemented.

Code

Code1(Time: O(n))

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // O(n)
        int leftBound = -1, rightBound = -1;
        int[] res = new int[]{leftBound, rightBound};
        if (nums == null || nums.length == 0) {
            return res;
        }
        
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] == target) {
                leftBound = mid;
                rightBound = mid;
                while (leftBound >= 0 && nums[leftBound] == target) {
                    leftBound--;
                }
                while (rightBound <= nums.length - 1 && nums[rightBound] == target) {
                    rightBound++;
                }
                return new int[]{leftBound+1, rightBound-1};
            }
        }
        return res;
    }
}

Code2(Time:O(log(n)))

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // O(log(n))
        int leftBound = -1, rightBound = -1;
        int[] res = new int[]{leftBound, rightBound};
        if (nums == null || nums.length == 0) {
            return res;
        }
        
        boolean exist = false;
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
                exist = true;
            }
        }
        res[0] = left;
        
        left = 0;
        right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                left = mid + 1;
            }
        }
        res[1] = right - 1;
        
        return exist ? res : new int[]{-1, -1};
    }
}

Don't try to accomplish all the thing in one condition, separate them and finally you may merge them. At first I tried

if (nums[mid] > target) {
    right = mid;
} else if (nums[mid] < target) {
    left = mid + 1;
} else {
    right = mid;
    exist = true;
}

with

if (nums[mid] >= target) {
    if (nums[mid] == target) {
        //xxx
    }
    right = mid;
} else if (nums[mid] < target) {
    left = mid + 1;
}

This lead me another road which adding complexity.