Search for a Range

参考了网上大神的model ,外加自己改进了点, 加上了自己的评注,至于说要不要做两次 或者三次 binary search,我就做了一次,也 ac了,以下是我的代码    public int[] searchRange(int[] A, int target) {         int[] res = new int[2];         res[0] = -1;         res[1] = -1;         if(A.length==0||A==null)            return res;         int l=0;         int h=A.length-1;         int mid=-1;//先要在外面定义一个 mid         while(l<=h){            mid=(l+h)/2;            if(A[mid]==target){                res[0]=mid;                res[1]=mid;                break;            }            else if(A[mid]<target)                     l=mid+1;                 else                     h=mid-1;         }         if(A[mid]!=target)            return res;//代表没有找到的情况         //以下就是在一定范围左右搜索的情况         int right=mid+1;         while(right<=A.length-1&&A[right]==target)               right++;         int left=mid-1;         while(left>=0&&A[left]==target)              left--;         res[0]=left+1;//跳出while loop的时候说明不相等,再+1补回来         res[1]=right-1;         return res;         } }

你虽然做了一次二分，但多做了两次线性查找，效率给变低了哦~~
如果给个500万的数组，所有元素都是1，那就能看出效果了。
还有这个例子：
0 1 1 ... (连续500万个) ... 1 2

做两次二分，一次是lower_bound，求出左界，一次是upper_bound，求出右界。这样才是O(log(N))，如果向左向右扫描，那就成O(N)了。