Search for a Range
1.最简单的想法，用最普通的二分查找，找到target,然后向左右扩张，大量的重复的target，就会出现O(n)效率。
class Solution {
public int[] searchRange(int[] A, int target) {
int ans[]=new int[];
int a= bserch(A,target);
if(a==-) {ans[]=-;ans[]=-; return ans;}
//left
int b=a-;
while(b>=&&A[b]==target) b--;
ans[]=b+;
b=a+;
while(b<=A.length-&&A[b]==target) b++;
ans[]=b-;
return ans;
}
public int bserch(int A[],int target)
{
int low=;
int end=A.length-;
while(low<=end)
{
int mid=(low+end)>>;
if(A[mid]==target) return mid;
else if(A[mid]<target) low=mid+;
else end=mid-;
}
return -;
}
}
2.二分查找加入第一个大的位置（上届），第一个大于等于它的位置（下界）
class Solution {
public int[] searchRange(int[] A, int target) {
int ans[]=new int[2];
int a= bserch(A,target);
if(a==-1) {ans[0]=-1;ans[1]=-1; return ans;}
//left
int b=a-1;
while(b>=0&&A[b]==target) b--;
ans[0]=b+1;
b=a+1;
while(b<=A.length-1&&A[b]==target) b++;
ans[1]=b-1;
return ans;
}
//其实难点就是A[mid]==target，如何调整low和high
public int bserch(int A[],int target)
{
int low=0;
int end=A.length-1;
while(low<=end)
{
int mid=(low+end)>>1;
if(A[mid]==target) return mid;
else if(A[mid]<target) low=mid+1;
else end=mid-1;
}
return -1;
}
//第一个大于target的
public int upperbound(int A[],int target) // the first one larger than target
{
int low=0;
int end=A.length-1;
while(low<=end)
{
int mid=(low+end)>>1;
if(A[mid]>target) end=mid-1;
else low=mid+1;
}
return low;
}
public int lowbound(int A[],int target) // the first one larger or equal target
{
int low=0;
int end=A.length-1;
while(low<=end)
{
int mid=(low+end)>>1;
if(A[mid]>=target) end=mid-1;
else low=mid+1;
}
return low;
}
}