https://oj.leetcode.com/problems/search-for-a-range/就是一个二分查找，没事练练手
public class Solution {
public int[] searchRange(int[] A, int target) {
int a[]=new int[2];
int ans=bSearch(A,target);
if(ans==-1)
{
a[0]=-1;
a[1]=-1;
return a;
}
else
{
int beg=ans;
int end=ans;
while(beg>=0&&(A[beg]==A[ans]))
{
beg--;
}
while(end<A.length&&(A[end]==A[ans]))
{
end++;
}
a[0]=beg+1;
a[1]=end-1;
return a;
}
}
public int bSearch(int[] A,int target)
{
int low=0;
int high=A.length-1;
while(low<=high)
{
int mid =(low+high)/2;
if(A[mid]==target)
{
return mid;
}
else if(A[mid]>target)
{
high=mid-1;
}
else
{
low=mid+1;
}
}
return -1;
}
}2.另外一种二分查找 beg=0 end=len; end指向的是最后一个元素的后面，
public class Solution {
public int[] searchRange(int[] A, int target) {
int a[]=new int[2];
int ans=bSearch(A,target);
if(ans==-1)
{
a[0]=-1;
a[1]=-1;
return a;
}
else
{
int beg=ans;
int end=ans;
while(beg>=0&&(A[beg]==A[ans]))
{
beg--;
}
while(end<A.length&&(A[end]==A[ans]))
{
end++;
}
a[0]=beg+1;
a[1]=end-1;
return a;
}
}
public int bSearch(int[] A,int target)
{
int low=0;
int high=A.length;
while(low<high) //low<high不能等于
{
int mid =(low+high)/2;
if(A[mid]==target)
{
return mid;
}
else if(A[mid]>target)
{
high=mid;
}
else
{
low=mid+1;
}
}
return -1;
}
}3.第一种方法的递归方式
public class Solution {
public int[] searchRange(int[] A, int target) {
int a[]=new int[2];
int ans=bSearch(A,target,0,A.length);
if(ans==-1)
{
a[0]=-1;
a[1]=-1;
return a;
}
else
{
int beg=ans;
int end=ans;
while(beg>=0&&(A[beg]==A[ans]))
{
beg--;
}
while(end<A.length&&(A[end]==A[ans]))
{
end++;
}
a[0]=beg+1;
a[1]=end-1;
return a;
}
}
public int bSearch(int[] A,int target,int low,int high)
{
while(low<high)
{
int mid =(low+high)/2;
if(A[mid]==target)
{
return mid;
}
else if(A[mid]>target)
{
bSearch(A,target,low,mid);
}
else
{
bSearch(A,target,mid,high);
}
}
return -1;
}
}