在二分搜索中，我们有两个比较，一个用于大于，另一个用于小于，否则是中间值。您将如何优化以便我们只需要检查一次？
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
}
我会首先尝试bsearch()标准功能。机会很好，它比你的方法更好。
bool binSearch(int array[], int key, int len)
{
int mid, low, high;
low = 0;
right = len - 1;
mid = low + (high-low)/2;
while ((low <= high) && (array[mid] != key)) {
if (key < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
mid = low + (high-low)/2;
}
if (array[mid] == key) {
return TRUE;
}
return FALSE;
}
using System;
namespace BinarySearchFast
{
public class BinarySearchFast
{
// csharp version, assuming compiler removes the inner branch, there should be almost no branching impact
// if index not found, returns ~(index of element to insert sorted) at.
public static int BinarySearchFast<T>(T[] array, T value) where T : IComparable<T>
{
if (array == null || array.Length == 0 || value == null)
{
return -1;
}
int start;
int mid;
int end;
int cmp = -1;
start = 0;
end = array.Length - 1;
mid = (start + end) / 2;
while (start <= end && (cmp = array[mid].CompareTo(value)) != 0)
{
// I *think* any good compiler will optimize this to avoid the branch by using a lerp based on cmp > 0 for end and start
// something like:
// end = lerp(end, mid - 1, cmp > 0);
// start = lerp(mid + 1, start, cmp > 0);
// but if not, the lerp could be inserted instead for C/C++, C# does not allow easy conversion of bool to int outside of System.Convert or an if statement.
if (cmp > 0)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
mid = (start + end) >> 1;
}
// could also replace with return lerp(~(++mid), mid, (cmp == 0));
return (cmp == 0 ? mid : ~(++mid));
}
}
}
BinarySearch = function (array, value)
{
var l = 0;
var r = array.length;
var mid;
while (l!=r)
{
mid = Math.round( (r+l)/2 )-1;
if(value > array[mid])
l=mid+1;
else
r=mid;
}
if(array[mid]==value)
return mid;
else
{
if( (mid < (array.length-1)) && (array[mid+1]==value) )
return mid+1;
else
return -1; // Not found
}
}
来源：http://calcs.appspot.com/docview?id=agVjYWxjc3IPCxIIRG9jdW1lbnQY0w8M
以您描述的方式尝试和优化是不可取的。来自Binary Search Algorithm article on Wikipedia：
大约一半时间，第一次测试将是真实的，因此只有一次比较a和b，但另一半时间它将是假的，并且第二次比较被迫。这是非常严重的，以至于某些版本被重新制作以便不进行第二次测试，因此在跨度减小到零之前不确定相等性，从而提前提前终止的可能性 - 记住大约一半的搜索时间发生在匹配值上，一次迭代超过限制。
通过使用诸如此类的命令，很容易使这个问题变得更糟（例如在3中）
if a = b then action3
else if a > b then action2
else action1;
这不会早期检测到相等（因为它可能看起来像），这将强制对除搜索的最后一次迭代之外的所有迭代执行两次比较。
有些语言，如Fortran，有一个三向比较，允许这一步完成一个比较，分为三个不同的部分（参见Three-way comparison example的第十行）。如果您的语言不支持三向测试（大多数语言不支持），则可以进行两次比较。
不过，我建议你从同一篇文章中查看iterative implementation。
我试图重建二进制搜索算法的优化步骤。我从这个迭代版本开始：
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<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1);
#if SIZE_MAX == UINT64_MAX
C(63) C(62) C(61)
C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif
C(31)
C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C
break;
default:
while( size > 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]<key ) p+=size-w-1;
switch( w ){
#define C(n) case ((size_t)1<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1);
#if SIZE_MAX == UINT64_MAX
C(63) C(62) C(61)
C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif
C(31)
C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C
}
*index=p-array; return p[0]==key;
}
我做的最后一步是简化案例标签[from：'（（size_t）1 << n）-1'到：'n']但我发现修改后的代码在我的旧PC上比以前的版本。
如果要优化二进制搜索算法，必须使用迭代替换递归。请参阅维基百科的示例。
如果您需要更多详细信息，请告诉我们。
在您发布的代码中，您可以删除最后一次比较。也就是说，如果key不小于array[mid]或大于array[mid]，那么根据定义它是相等的。所以你的代码变成：
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
return TRUE; // Found
另请注意，我删除了最后一行。在您的原始代码中，return FALSE;不可能被执行。我会假设您在binSearch的开头检查，检查left <= right。
在C中，没有办法在小于，等于，大于的情况下进行三向比较/分支，因此您必须进行两次比较以在三种可能性中进行选择。
对于整数而言，没关系，不要这样做。
对于更昂贵的比较，对于<，=，>使用-1,0,1，就像在C库函数strcmp或Java的compareTo（）中一样。
// Optimized Binary Search Implementation
int binsearch(int* data, int size, int val)
{
int result = -1;
int start, mid, end;
start = 0;
end = size - 1;
mid = (start + end) >> 1;
while (start <= end && data[mid] != val)
{
if (data[mid] > val)
end = mid - 1;
else
start = mid + 1;
mid = (start + end) >> 1;
}
if (val == data[mid])
result = mid;
return result;
}
Ganesh M - 如果数组中不存在该键，那么您的函数将被卡在一个永无止境的循环中。它永远不会返回FALSE。
如果密钥不存在，找到插入点的最佳方法是什么？
<，==和>的条件“if cascade”会计只会返回TRUE，或者继续永远计算。
我需要最佳条件来确定密钥何时被隔离为不存在。
我知道这会减慢搜索速度，但我希望减少它的速度。
使用log（N）/ log（2）似乎是一个好主意，但是当N不是2的幂时，事情就会变得混乱。
也许，我应该选择一个功率为2的数组，并使用一个简单的while循环？
检查中点==是否绑定增加了比较次数？
这是K＆R第二版的一个练习题。
While(low <= high && arr[mid]!=num)
{
if(arr[mid] > num)
{
low = mid+1;
}
else
{
high = mid-1;
}
mid = (low+high)/2;
}
if(arr[mid] == num)
{
printf("found the ugly number");
return mid;
}