binary search
/*
while (left <= right) 8(left) 8 10(right)
理解binary search变形能做什么
找到相同的后move towards left side to find the first same element
也可以while(target == nums[mid--])来找first same element,但是用binary search才满足o(logn)
*/
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = findStartingIndex(nums, target);
res[1] = findEndingIndex(nums, target);
return res;
}
public int findStartingIndex(int[] nums, int target) {
int left = 0, right = nums.length - 1, res = -1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
res = mid;
}
if(nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return res;
}
public int findEndingIndex(int[] nums, int target) {
int left = 0, right = nums.length - 1, res = -1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
res = mid;
}
if(nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
}