34. Find First and Last Position of Element in Sorted Array
Binary Search. Time = O(logn), space = O(1);
先二分搜索最左位置，再二分搜索最右位置。和普通二分搜索相比，要提前一步停下来。
找 First/Last element 的 termination condition: 当 left 和 right 相邻的时候，跳出 while 循环，再判断 left 和 right 究竟哪个是最终答案。
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = {-1, -1};
if (nums == null || nums.length == 0) {
return res;
}
int left = 0;
int right = nums.length - 1;
while (left < right - 1) { // 提前一步停下来
int mid = left + (right - left)/2;
if (nums[mid] >= target) {
right = mid; // when nums[mid] == target, do not stop, keep checking to left.
} else {
left = mid;
}
}
if (nums[left] == target) {
res[0] = left;
} else if (nums[right] == target) {
res[0] = right;
} else {
return res;
}
right = nums.length - 1;
while (left < right - 1) {
int mid = left + (right - left)/2;
if (nums[mid] <= target) {
left = mid; // when nums[mid] == target, do not stop, keep checking to right.
} else {
right = mid;
}
}
if (nums[right] == target) {
res[1] = right;
} else if (nums[left] == target) {
res[1] = left;
} else {
return res;
}
return res;
}
}