[leetcode] Search For a range

binary search一个特点就是 当condition 是 left <= right的时候 在结尾没找到 left会给该插入的位置... right会给插入的位置的前一位 找左边：一个变化就是 当找到的时候 push right=mid-1,直到 [left,right]没有target..这时候结尾return left给出的插入的位置会是right+1...而现实中是[left, right]+[target, ...., end] target index 刚好就是right+1 右边同理 但是是找应该插入位置的前一个 因为[start...target]+[left,right] 结尾return left给出的插入位置是left..而target 在left-1处

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 30 31 32 33 34 35 36 37

public class Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = findLeft(nums, target); result[1] = findRight(nums, target); return result; } int findLeft(int nums[], int target){ int left = 0; int right = nums.length-1; while (left <= right){ int mid = (left+right)/2; if (nums[mid] >= target){ right = mid - 1; }else{ left = mid + 1; } } if (left >= 0 && left <= nums.length-1 && nums[left] == target) return left; return -1; } int findRight(int nums[], int target){ int left = 0; int right = nums.length-1; while (left <= right){ int mid = (left+right)/2; if (nums[mid] <= target){ left = mid + 1; }else{ right = mid - 1; } } if (left >= 1 && left <= nums.length && nums[left-1] == target) return left-1; return -1; } }