在C++中使用二分查找算法可以通過以下步驟實現:
首先,確定要查找的目標元素target以及待查找的有序數組arr。
定義兩個變量low和high,分別表示查找范圍的最低和最高索引。
在while循環中,當low小于等于high時,進行查找操作。
在循環體內,計算中間索引mid = (low + high) / 2,并取出arr[mid]的值。
根據arr[mid]與target的大小關系,更新low和high的值,縮小查找范圍。
如果找到目標元素,返回目標元素的索引;如果未找到目標元素,返回-1表示未找到。
以下是一個使用二分查找算法查找目標元素target在有序數組arr中的索引的示例代碼:
#include <iostream>
#include <vector>
int binarySearch(std::vector<int>& arr, int target) {
int low = 0;
int high = arr.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 6;
int result = binarySearch(arr, target);
if (result != -1) {
std::cout << "Target element found at index: " << result << std::endl;
} else {
std::cout << "Target element not found in the array" << std::endl;
}
return 0;
}
在上面的示例代碼中,我們定義了一個名為binarySearch的函數,用于執行二分查找算法。我們首先定義了一個有序數組arr和目標元素target,然后調用binarySearch函數進行查找,并輸出結果。