二進位制搜尋排序的數字

使用虛擬碼在數字上顯示二進位制搜尋是最簡單的

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 實現等實現，以降低真正大輸入溢位的風險，這也是一個好主意。