Set first to 0
Set last to the last subscript in the array
Set found to false
Set position to -1
While found is not true and first is less than or equal to last
Set middle to the subscript halfway between first and last
If array[middle] equals the desired value
Set found to true
Set position to middle
Else If array[middle] is greater than the desired value
Set last to middle - 1
Else
Set first to middle + 1
End If
End While
Return position
該演算法使用 3 個索引變數：first、last 和 middle。first 和 last 變數標記當前正在搜尋的陣列部分的邊界。它們用陣列的第一個和最後一個元素的下標進行初始化。middle 則是在 first 和 last 元素之間大約中點位置的元素的下標，該值的計算方法就是釆用 first 和 last 相加求和然後除以 2，結果將被儲存在 middle 變數中。int binarySearch(const int array[], int size, int value)
{
int first = 0, //第一個陣列元素
last = size - 1, //最後一個陣列元素
middle, //搜尋的中點
position = -1; //搜尋值的位置
bool found = false; // 標記
while (!found && first <= last)
{
middle = (first + last) / 2; // 計算中點
if (array[middle] == value) // 如果在中點發現值
{
found = true;
position = middle;
}
else if (array [middle] > value) // 如果值在下半部分
last = middle - 1;
else
first = middle + 1; //如果值在上半部分
}
return position;
}
下面的程式是一個使用 binarySearch 函數的完整程式。它將搜尋一個包含員工 ID 號的陣列，以查詢特定的值。
//This program performs a binary search on an integer array whose elements are in ascending order.
#include <iostream>
using namespace std;
//Function prototype
int binarySearch(const int [], int, int);
const int SIZE = 20;
int main()
{
// Create an array of ID numbers sorted in ascending order
int IDnums[SIZE] = {101, 142, 147, 189, 199, 207, 222,234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600 };
int empID, // Holds the ID to search for
results;//Holds the search results
// Get an employee ID to search for
cout << "Enter the employee ID you wish to search for: ";
cin >> empID;
// Search for the ID
results = binarySearch(IDnums, SIZE, empID);
// If binarySearch returned -1, the ID was not found
if (results == -1)
cout << "That number does not exist in the array.n";
else
{
// Otherwise results contains the subscript of
// the specified employee ID in the array
cout << "ID " << empID << " was found in element " << results << " of the array.n";
}
return 0;
}
int binarySearch(const int array[], int size, int value)
{
int first = 0, // First array element
last = size - 1, // Last array element
middle, // Midpoint of search
position = -1; // Position of search value
bool found = false; // Flag
while (!found && first <= last)
{
middle = (first + last) / 2; // Calculate midpoint
if (array[middle] == value) // If value is found at mid
{
found = true;
position = middle;
}
else if (array[middle] > value) // If value is in lower half
last = middle - 1;
else
first = middle +1; // If value is in upper half
}
return position;
}
程式輸出結果：
Enter the employee ID you wish to search for: 199
ID 199 was found in element 4 of the array.