| Problem
Given a sorted array of n integers, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Example
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Challenge
O(log n) time.
Note
首先，建立二元结果数组res，起点start，终点end。
二分法求左边界：
当中点小于target，start移向中点，否则end移向中点；
先判断起点，再判断终点是否等于target，如果是，赋值给res[0]。
二分法求右边界：
当中点大于target，end移向中点，否则start移向中点；
先判断终点，再判断起点是否等于target，如果是，赋值给res[1]。
返回res。
Solution- public class Solution {
- public int[] searchRange(int[] A, int target) {
- int []res = {-1, -1};
- if (A == null || A.length == 0) return res;
- int start = 0, end = A.length - 1;
- int mid;
- while (start + 1 < end) {
- mid = start + (end - start) / 2;
- if (A[mid] < target) start = mid;
- else end = mid;
- }
- if (A[start] == target) res[0] = start;
- else if (A[end] == target) res[0] = end;
- else return res;
- start = 0;
- end = A.length - 1;
- while (start + 1 < end) {
- mid = start + (end - start) / 2;
- if (A[mid] > target) end = mid;
- else start = mid;
- }
- if (A[end] == target) res[1] = end;
- else if (A[start] == target) res[1] = start;
- else return res;
- return res;
- }
- }
- public class Solution {
- public int[] searchRange(int[] nums, int target) {
- int n = nums.length;
- int[] res = {-1, -1};
- int start = 0, end = n-1;
- while (nums[start] < nums[end]) {
- int mid = start + (end - start) / 2;
- if (nums[mid] > target) end = mid - 1;
- else if (nums[mid] < target) start = mid + 1;
- else {
- if (nums[start] < target) start++;
- if (nums[end] > target) end--;
- }
- }
- if (nums[start] == target) {
- res[0] = start;
- res[1] = end;
- }
- return res;
- }
- }
| 
