查找算法笔记（C++版）

1.顺序查找

时间复杂度：O(n)

代码：

代码语言：javascript复制

//顺序查找
int sequentialSearch(int* list, int n, int x)
{
    for (int i = 0; i < n; i  )
    {
        if (list[i] == x)
            return i;
    }
    return -1;
}

测试代码：

代码语言：javascript复制

int main(void)
{
    int list[] = { 1,3,5,7,9,2,4,6,8,0 };//可以是无序数组
    cout << "list[]:";
    for (int i = 0; i < 10; i  )
        cout << list[i] << " ";
    cout << endl;

    int x = 8;
    int i = sequentialSearch(list, 10, x);

    if (i < 0) cout << "未找到" << endl;
    else cout << "list[" << i << "]中找到" << x << endl;
    return 0;
}

运行结果：

代码语言：javascript复制

list[]:1 3 5 7 9 2 4 6 8 0
list[8]中找到8
请按任意键继续. . .

2.二分查找

时间复杂度：O(logn)

代码：

代码语言：javascript复制

//二分查找
int binSearch(int* list, int n, int x)
{
    int lo = 0, hi = n - 1;
    while (lo <= hi)
    {
        //int mid = (lo   hi) / 2;//此句代码在min和max很大时，会出现溢出！
        int mid = (lo   ((hi - lo) >> 1));
        if (x > list[mid]) 
            lo = mid   1;
        else if(x < list[mid]) 
            hi = mid - 1;
        else //(x == list[mid])已找到
            return mid;
    }
    return -1;
}

递归形式：

代码语言：javascript复制

//二分查找（递归方式）
int binSearch_R(int* list, int lo, int hi, int x)
{
    if (lo <= hi)
    {
        int mid = (lo   ((hi - lo) >> 1));
        if (x > list[mid])
            return(binSearch_R(list, mid   1, hi, x));
        else if (x < list[mid])
            return(binSearch_R(list, lo, mid - 1, x));
        else //(x == list[mid])已找到
            return mid;
    }
    return -1;
}

测试代码：

代码语言：javascript复制

int main(void)
{
    int list[] = {1,3,5,7,9,11,13,15,17,19};//前提：有序数组！
    cout << "list[]:";
    for (int i = 0; i < 10;i  )
        cout << list[i] << " ";
    cout << endl;

    int x = 15;
    //int i = binSearch(list, 10, x);
    int i = binSearch_R(list, 0, 10, x);

    if (i < 0) cout << "未找到" << endl;
    else cout << "list[" << i << "]中找到" << x << endl;
    return 0;
}

运行结果：

代码语言：javascript复制

list[]:1 3 5 7 9 11 13 15 17 19
list[7]中找到15
请按任意键继续. . .

此文首发于我的CSDN:https://blog.csdn.net/hbsyaaa/article/details/89787884

sdn 递归

0 人点赞