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:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
/** * 从前往后找，从后往前找 * @param nums * @param target * @return */ public static int[] search1(int[] nums, int target) { int[] result = new int[]{-1,-1}; if(nums == null || nums.length == 0) return result; for(int i = 0; i < nums.length; i++) { if(nums[i] == target) { result[0] = i; break; } } if(nums[0] == -1) return result; for(int i = nums.length-1; i>=0;i--) { if(nums[i] == target) { result[1] =i; break; } } return result; } /** * 二分查找 * @param nums * @param target * @return */ public static int[] search2(int[] nums, int target) { int[] result = new int[]{-1,-1}; if(nums == null || nums.length == 0) return result; int leftIndex = getIndex(nums,target,true); if(leftIndex == nums.length || nums[leftIndex] != target) return result; int rightIndex = getIndex(nums,target,false) - 1; result[0] = leftIndex; result[1] = rightIndex; return result; } public static int getIndex(int[] nums, int target, boolean flag) { int lo = 0; int high = nums.length; while(lo < high) { int mid = (lo + high) / 2; if(nums[mid] > target || (flag && target == nums[mid])) { high = mid ; } else { lo = mid + 1; } } return lo; } /** * 二分查找 * @param nums * @param target * @return */ public static int[] search3(int[] nums, int target) { int[] result = new int[]{-1,-1}; if(nums == null || nums.length == 0) return result; result[0] = FindFirst(nums,target); result[1] = FindLast(nums,target); return result; } /** * 搜索左边第一个为target的元素 * @param nums * @param target * @return */ public static int FindFirst(int[] nums, int target) { int index = -1; int lo = 0; int hi = nums.length - 1; while(lo <= hi) { int mid = (lo + hi) / 2; if(nums[mid] >= target) { hi = mid - 1; } else { lo = mid + 1; } if(nums[mid] == target) index = mid; } return index; } /** * 寻找最后一个target的索引 * @param nums * @param target * @return */ public static int FindLast(int[] nums,int target) { int index = -1; int lo = 0; int hi = nums.length - 1; while(lo <= hi) { int mid = (lo + hi) / 2; if(nums[mid] <= target) { lo = mid +1; } else { hi = mid - 1; } if(nums[mid] == target) index = mid; } return index; }