The problem

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

If no target value exists in the array, return [-1, -1].

Train of thought

The basic idea is to use binary search. If nums[mid] is target, check whether nums[mid] is target. If nums[mid] is target, check whether nums[mid] is target. Otherwise, return directly. And the same thing happens when you find the last one.

code

class Solution { public int[] searchRange(int[] nums, int target) { int low = findLowIndex(nums, target); int high = findHighIndex(nums, target); return new int[] {low, high}; } private int findLowIndex(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int low = 0; int high = nums.length - 1; while (low <= high) { int mid = (low + high) / 2; If (mid [mid] == target) {if (mid >= low && mid [mid] == target) {high = mid; } else { return mid; } } if (nums[mid] > target) { high = mid - 1; } if (nums[mid] < target) { low = mid + 1; } } return -1; } private int findHighIndex(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int low = 0; int high = nums.length - 1; while (low <= high) { int mid = (low + high) / 2; if (nums[mid] == target) { if (mid + 1 <= high && nums[mid + 1] == target) { low = mid + 1; } else { return mid; } } if (nums[mid] > target) { high = mid - 1; } if (nums[mid] < target) { low = mid + 1; } } return -1; }}Copy the code

Code 2

public class Solution { public int[] searchRange(int[] nums, int target) { int[] result = {-1, -1}; int start = 0; int end = nums.length - 1; int mid = 0; while (start <= end) { mid = start + ((end - start) >>> 1); If (target <= nums[mid]) {end = mid; if (target <= nums[mid]) {end = mid; } else { //target >= nums[mid] start = mid + 1; } } if (start < nums.length && nums[start] == target) { result[0] = start; end = nums.length - 1; while (start <= end) { mid = start + ((end - start) >>> 1); if (target < nums[mid]) { end = mid - 1; } else { start = mid + 1; } } result[1] = end; return result; } return result; }}Copy the code

The official

Select the first subscript greater than or equal to target and the first subscript greater than target -1.

If you look for the first index greater than or equal to target, you just go left when greater than or equal to the old dichotomy.

class Solution { public int[] searchRange(int[] nums, int target) { int left = binarySearch(nums, target, true); int right = binarySearch(nums, target, false) - 1; if (left <= right && nums[left] == target && nums[right] >= target) { return new int[] {left, right}; } return new int[] {-1, -1}; } private int binarySearch(int[] nums, int target, Boolean left) {int low = 0, high = nums.length - 1, res = nums.length; while (low <= high) { int mid = (low + high) / 2; if (nums[mid] > target || (left && nums[mid] >= target)) { high = mid - 1; res = mid; } else { low = mid + 1; } } return res; }}Copy the code

The complexity of the

Time complexity: O(logn) Space complexity: O(1)

Hard advertising

Welcome to the public account: Double6