Find First And Last Position of Element in Sorted Array
给一个排序好的数组, 里面可能有重复的元素, 在里面找一个元素, 如果有重复的, 找到开始和结束的index. 就是基础的带重复的二叉搜索,
public class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0 || nums == null)
return null;
int[] range = new int[]{nums.length, -1};
bst(nums, 0, nums.length-1, target, range);
if(range[0] > range[1])
range[0] = -1;
return range;
}
public void bst(int[] nums, int l, int r, int target, int[] range) {
if(l > r)
return;
int mid = l + (r - l) / 2;
if(target == nums[mid]) {
if(mid < range[0]){
range[0] = mid;
bst(nums, l, mid-1, target, range);
}
if(mid > range[1]){
range[1] = mid;
bst(nums,mid+1,r, target, range);
}
}else if(target > nums[mid]){
bst(nums,mid+1, r, target,range);
}else
bst(nums,l,mid-1,target,range);
}
}