Find First And Last Position of Element in Sorted Array
给一个排序好的数组, 里面可能有重复的元素, 在里面找一个元素, 如果有重复的, 找到开始和结束的index. 就是基础的带重复的二叉搜索,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
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); } } |