二分查找算法

二分查找算法
问题一、在一个有序的序列(不降序列)中查找指定值的算法,查找成功返回它所在的位置,否则返回-1
int binarySearch(int a[],int l,int r,int x)
{
     int ans=-1;
     while(l<=r)
     {
          int m=l+(r-l)/2;
          if (a[m]==x)
          {
               ans=m;break;
          }
          if (a[m]<x)
               l=m+1;
          else
               r=m-1;
         }   
         return ans;
}
问题二、如果要查找指定值的最早的下标,如何实现
int binarySearch(int a[],int l,int r,int x)
{
     int ans=-1;
    while(l<=r)
    {
          int m=l+(r-l)/2;
          if (a[m]==x)
         {
               ans=m;r=m-1;
         }
         if (a[m]<x)
              l=m+1;
         else
             r=m-1;
         }
         return ans;
}
问题三、要查找第一个大于等于指定值的下标?
int binarySearch(int a[],int l,int r,int x)
{
      int ans=-1;
      while(l<=r)
     {
          int m=l+(r-l)/2;
         if (a[m]>=x)
         {
              ans=m;r=m-1;
         }
        else
              l=m+1;
        }
        return ans;
}
问题四、要查找第一个大于指定值的下标?
int binarySearch(int a[],int l,int r,int x)
{
     int ans=-1;
     while(l<=r)
     {
          int m=l+(r-l)/2;
          if (a[m]>x)
          {
               ans=m;r=m-1;
          }
          else
               l=m+1;
     }
     return ans;
}

 

上一篇:BZOJ1927: [Sdoi2010]星际竞速(最小费用最大流 最小路径覆盖)


下一篇:Unity做简单的有限元分析效果