Given an array of integers 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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].两个二分查找法，分别查找最左边和最右边的target。
public class Solution { public int[] searchRange(int[] nums, int target) { int[] ret = new int[2]; if(nums.length == 0 || nums == null) { ret[0] = ret[1] = -1; return ret; } // left search int start = 0; int end = nums.length - 1; int middle; while (start + 1 < end) { middle = start + (end - start) / 2; if (nums[middle] == target) { end = middle; // end赋值 } if (nums[middle] < target) { start = middle; } if (nums[middle] > target) { end = middle; } } // 先比较start，再比较end if (nums[start] == target) { ret[0] = start; } else if (nums[end] == target) { ret[0] = end; } else { ret[0] = ret[1] = -1; return ret; } // right search start = 0; end = nums.length - 1; while (start + 1 < end) { middle = start + (end - start) / 2; if (nums[middle] == target) { start = middle; // start赋值 } if (nums[middle] < target) { start = middle; } if (nums[middle] > target) { end = middle; } } // 先比较end，再比较start if (nums[end] == target) { ret[1] = end; } else if (nums[start] == target) { ret[1] = start; } else { ret[1] = ret[1] = -1; return ret; } return ret; } }