二分查找|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;
}
最后修改：2024 年 08 月 14 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏