二分查找|Binary search
时间复杂度
$$ O(logn) $$
说明:对目标值x在有序区间(low,high)中进行查找，如果x>array[(low+high)//2]则low = (low+high)//2 + 1，如果x<array[(low+high)//2]则high= (low+high)//2 -1
//2024/7/12
#include <iostream>
using namespace std;
void print_array(int* arr, int size) {
//打印数组
cout << "array={ ";
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << "}" << endl;
}
int binary_search(int* array, int size, int target) {
//二分查找 提供 数组地址 数组长度 以及查找目标
int low = 0;
int high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] < target) {
low = mid + 1;
}
else if (array[mid] > target) {
high = mid - 1;
}
else {
return mid;
}
}
return -1;
}
int main() {
//数组基本信息
int array1[] = { 11,22,33,44,55,66,77,88,99 };
int sizeArray = sizeof(array1) / sizeof(array1[0]);
//打印数组
print_array(array1, sizeArray);
//使用二分查找
int target = 32;
int result = binary_search(array1, sizeArray, target);
if (result != -1) {
cout << "查找成功" << endl << "位于下标" << result << "处" << endl;
}
else {
cout << "查找失败，数组中可能不存在该元素" << endl;
}
return 0;
}
