34. 在排序数组中查找元素的第一个和最后一个位置

leetcode链接：
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

方案一

特殊处理，数组为空的时候。

int left = 0,
	right = nums.length - 1,
	mid = 0,
	nums_size = nums.length - 1,
	start = -1,
	end = -1;
if (nums_size == -1)
	return new int[]{start, end};
while(left <= right) {
	mid = left + (right - left) / 2;
	if (nums[mid] > target) {
		right = mid - 1;
	} else if(nums[mid] == target) {
		start = end = mid;
		while (start > 0) {
			if (nums[--start] != target)
			{
				start++;
				break; 
			}
		}
		while (end < nums_size) {
			if (nums[++end] != target)
			{
				end--;
				break;
			}
		}
		return new int[]{start, end};
	} else {
		left = mid + 1;
	}
}

return new int[]{start, end};

结果

• 88/88 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 18.58 % of java submissions (44.9 MB)

分析

时间复杂度：
O( n )
极端情况：当数组中的所有数据都为target的时候

空间复杂度：
O( 1 )

几乎最优方案

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/

与方案一的区别：其利用二分法查找其上下界，其实使用了两次二分法。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。