二分搜索 | 恨了没 你摇头轻叹谁让你蹙着眉
Cobb 567 1

二分搜索



#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <algorithm>

/*
*  函数功能: 二分搜索算法
*  用法: 有序的数组中
*  时间复杂度:平均O(logn)、最差O(logn)、最优O(1)
*  空间复杂度:O(1)
*/
int BinarySearch(int arr[], int size, int val)
{
    int f = 0;
    int l = size - 1;

    while (f <= l)
    {
        int mid = (f + l) / 2;

        if (arr[mid] == val)
        {
            return mid;
        }
        else if (arr[mid] < val)
        {
            //舍弃前一半,从mid下一位开始
            f = mid + 1;
        }
        else
        {
            //舍弃后一半,从mid前一位开始
            l = mid - 1;
        }
    }
    return -1;
}



// 提供一个函数接口,在数组中搜索一个元素   线性搜索
int FindValue(int arr[], int size, int val)
{
    for (int i = 0; i < size; i++)  // O(n)
    {
        if (arr[i] == val)
        {
            return i;
        }
    }
    return -1;
}


int main()
{
    long start, end;
    int idx;
    srand(time(0));

    int* arr = (int*)malloc(10000000 * sizeof(int));

    for (int i = 0; i < 10000000; i++)
    {
        arr[i] = rand();
    }

    arr[987650] = 12;
    std::sort(arr, arr + 10000000); 

    start = clock();
    idx = FindValue(arr, 10000000, 12);
    end = clock();
    printf("FindValue time:%dms idx:%d\n", end - start, idx);

    start = clock();
    idx = BinarySearch(arr, 10000000, 12);
    end = clock();
    printf("BinarySearch time:%dms idx:%d\n", end - start, idx);

}

评论区