优化二进制搜索算法

在二分搜索中,我们有两个比较,一个用于大于,另一个用于小于,否则是中间值.您将如何优化以便我们只需要检查一次？

bool binSearch(int array[], int key, int left, int right)
{

    mid = left + (right-left)/2;
    if (key < array[mid])
        return binSearch(array, key, left, mid-1);
    else if (key > array[mid])
        return binSearch(array, key, mid+1, right);
    else if (key == array[mid])
        return TRUE; // Found

    return FALSE; // Not Found
}

quinmars.. 17

我会首先尝试bsearch()标准函数.机会很好,它比你的方法更好.

我会首先尝试bsearch()标准函数.机会很好,它比你的方法更好.

以您描述的方式尝试和优化是不可取的.来自维基百科上的二进制搜索算法文章:

大约一半时间,第一次测试将是真实的,因此只有一次比较a和b,但另一半时间它将是假的,并且第二次比较被迫.这是非常严重的,以至于某些版本被重新制作以便不进行第二次测试,因此在跨度减小到零之前不确定相等性,从而提前提前终止的可能性 - 记住大约一半的搜索时间发生在匹配值上,一次迭代超过限制.

通过使用诸如此类的命令,很容易使这个问题变得更糟(例如在3中)

if a = b then action3
 else if a > b then action2
  else action1;

这不会早期检测到相等(因为它可能看起来像),这将强制对除搜索的最后一次迭代之外的所有迭代执行两次比较.

有些语言(如Fortran)具有三向比较,允许通过一个分支完成此步骤,该比较分支到三个不同的部分(参见三向比较示例的第十行).如果您的语言不支持三向测试(大多数语言不支持),则可以进行两次比较.

我会建议您检查出的迭代实现从同一篇文章,虽然.

我试图重建二进制搜索算法的优化步骤.我从这个迭代版本开始:

int binsearch_1( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  int found=0;
  while( size > 0 ){
    size_t w=size/2;
         if( p[w] <  key  ){ p+=w+1; size-=w+1; }
    else if( p[w] >  key  ){         size =w;   }
    else  /* p[w] == key */{ p+=w; found=1; break; }
  }
  *index=p-array; return found;
}

消除循环中的比较:

int binsearch_2( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 0 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else size =w;
  }
  *index=p-array; return p[0]==key;
}

从循环中展开小尺寸:

int binsearch_3( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 8 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
  }
  if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
  if( size==7 ){ if( p[4] <=  key ){ p+=4; size=3; } else size=3; }
  if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
  if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
  if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
  if( size==3 ){ if( p[2] <=  key ){ p+=2; size=1; } else size=1; }
  if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }
  if( size==1 ){ if( p[1] <=  key ){ p+=1;         }              }
  *index=p-array; return p[0]==key;
}

重新排序if语句,将特殊情况[size == pow(2,N)-1]移到最后:

int binsearch_4( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 8 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
  }
  if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
  if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
  if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
  if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
  if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }

  if( size==7 ){ if( p[4] <=  key ){ p+=4; size=3; } else size=3; }
  if( size==3 ){ if( p[2] <=  key ){ p+=2; size=1; } else size=1; }
  if( size==1 ){ if( p[1] <=  key ){ p+=1;         }              }
  *index=p-array; return p[0]==key;
}

将if语句更改为switch语句:

int binsearch_5( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 8 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
  }
  if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
  if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
  if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
  if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
  if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }

  switch(size){
    case 7: if( p[4] <= key ) p+=4;
    case 3: if( p[2] <= key ) p+=2;
    case 1: if( p[1] <= key ) p+=1;
  }
  *index=p-array; return p[0]==key;
}

扩展switch语句以处理所有特殊情况:

int binsearch_6( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  switch( size ){
#define C(n) case ((size_t)1< 0 ){
        size_t w=size/2;
        if( p[w] < key ){ p+=w+1; size-=w+1; } else size=w;
      }
  }
  *index=p-array; return p[0]==key;
}

从代码中消除一般案例处理:[w是最小的数字:w == pow(2,N)-1; 大小<= 2*(w + 1)]

int binsearch_7( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  size_t w=(size-1)>>1; w|=w>>1; w|=w>>2; w|=w>>4; w|=w>>8; w|=w>>16;
#if SIZE_MAX == UINT64_MAX
  w|=w>>32;
#endif
  if( p[w]

我做的最后一步是简化案例标签[from:'((size_t)1 << n)-1'到:'n']但我发现修改后的代码在我的旧PC上比以前的版本.