二进制搜索排序的数字

使用伪代码在数字上显示二进制搜索是最简单的

int array[1000] = { sorted list of numbers };
int N = 100;  // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for

low = 0;
high = N -1;
while(low < high)
{
    mid = (low + high)/2;
    if(array[mid] < x)
        low = mid + 1;
    else
        high = mid;  
}  
if(array[low] == x)
    // found, index is low
else
    // not found

不要尝试通过将 array [mid]与 x 进行比较来提前返回。额外的比较只能减慢代码速度。请注意，你需要将一个添加到低位以避免被整数除法陷入困境。

有趣的是，上面的二进制搜索版本允许你在数组中找到 x 的最小出现位置。如果数组包含 x 的重复项，则可以稍微修改算法，以便通过简单地添加到 if 条件来返回 x 的最大出现：

while(low < high)
    {
        mid = low + ((high - low) / 2);
        if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
            low = mid + 1;
        else
            high = mid;  
    }

请注意，不是做 mid = (low + high) / 2，而是尝试使用 mid = low + ((high - low) / 2) 进行 Java 实现等实现，以降低真正大输入溢出的风险，这也是一个好主意。