Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
思路：BS的变形，
mid = lo+(hi-lo)/2;已经是bias to the left /* * BS 的变形 * 分别找到begin 和end */ public class Solution { public int[] searchRange(int[] A, int target) { int lo=0, hi=A.length-1, mid; int[] rst = new int[2]; rst[0]=-1;rst[1]=-1; if(A.length == 0) return rst; // begin // terminate loop when lo==hi==begin while(lo < hi) { mid = lo+(hi-lo)/2; if(A[mid] < target) lo=mid+1; else hi=mid; } if(A[lo] == target) rst[0] = lo; // end, baised to right hi=A.length-1; while(lo < hi) { mid = lo+(hi-lo+1)/2; if(A[mid] > target) hi=mid-1; else lo=mid; } if(A[lo] == target) rst[1] = lo; return rst; } }
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0
思路：对标志BS返回值的理解，处理好边界情况
/* * 如果不在首尾，那么ＢＳ找到的就是适合ｔａｒｇｅｔ的位置 */ public class Solution { public int searchInsert(int[] A, int target) { int i = bs(A, 0, A.length-1, target); if(i == 0 && A[0] < target) return 1; if(i == A.length-1 && A[i] > target) return A.length-1; return i; } public int bs(int[] A, int lo, int hi, int target) { int mid, cmp; while(lo <= hi) { mid = lo+(hi-lo)/2; cmp = A[mid]-target; if(cmp == 0) return mid; else if(cmp > 0) hi=mid-1; else lo=mid+1; } return lo; } }
