数据结构笔记(七):线性表的查找之顺序查找与二分查找

发布于 / 程序猿 / 4 条评论

本文简单介绍查找线性表(顺序表)中元素时常用的顺序查找二分查找,若文中存在错误,敬请指出,感谢阅读。

查找(Searching)的定义是:给定一个值Key,在含有n个结点的表中找出关键字等于给定值Key的结点。若找到,则查找成功,返回该结点的信息或该结点在表中的位置;否则查找失败,返回相关的指示信息。

顺序查找

基本知识

基本思想:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键宇和给定值Key相比较。若当前扫描到的结点关键字与Key相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。

顺序查找方法既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构(使用单链表作存储结构时,扫描必须从第一个结点开始)。

效果演示

3,4,1,2,5,9,7,6中寻找1的位置。

算法实现

#include <iostream>
using namespace std;

int search1(int a[], int n, int key) // 顺序查找
{
    a[0] = key; // 监视哨
    int i;
    for (i = n; a[i] != key; --i) // 从第n个元素开始逆序查找
        ;
    return i; // 返回0表示查询失败
}

int search2(int a[], int n, int key) // 同上
{
    a[0] = key; // 监视哨
    int i = n;
    while(a[i] != key)
        --i;
    return i;
}

int main()
{
    int n;
    int a[100];
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int key; // 查询的值
    while(cin >> key)
    {
        cout << search1(a, n, key) << endl; // 输出查询位置
        cout << search2(a, n, key) << endl;
    }
    return 0;
}
8 // 输入长度为8的数组
3 4 1 2 5 9 7 6
4 // 查找4返回2(查询成功)
2
2
5 // 查找5返回5(查询成功)
5
5
9 // 查找9返回6(查询成功)
6
6
10 // 查找10返回0(查询失败)
0
0

算法分析

算法中监视哨a[0]的作用:为了在for循环中省去判定防止下标越界的条件i≥1。

顺序查找的优点:算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。

顺序查找的缺点:查找效率低,因此,当n较大时不宜采用顺序查找。

时间复杂度O(n)


二分查找

基本知识

二分查找又称折半查找,它是一种效率较高的查找方法。

二分查找要求

  • 存储在数组中
  • 有序排列

二分查找的基本思想

将查找的键和子数组的中间键作比较,如果被查找的键小于中间键,就在左子数组继续查找;如果大于中间键,就在右子数组中查找,否则中间键就是要找的元素。

  • a[left..right]是当前的查找区间
  • 首先确定该区间的中点位置:mid = (left+right) / 2,即mid = (left+right) >> 1,有时候也写成left + ((right-left) >> 1),不解释。
  • 然后将待查的Key值与a[mid]比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找。
  • ①若a[mid]>Key,则由表的有序性可知a[mid..n]均大于Key,因此若表中存在关键字等于Key的结点,则该结点必定是在位置mid左边的子表a[1..mid-1]中,故新的查找区间是左子表a[1..mid-1]。
  • ②若a[mid]<Key,则要查找的Key必在mid的右子表a[mid+1..n]中,即新的查找区间是右子表a[mid+1..n]。
  • 因此,从初始的查找区间a[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。

效果演示

1, 2, 4, 5, 6, 8, 11, 17寻找11的位置。

算法实现

  • 查询数组元素位置从0开始返回-1表示未找到
#include <iostream>
#include <algorithm>
using namespace std;

int Binary_Search(int a[], int n, int key) // 数组下标从0开始
{
    int left = 0, right = n - 1;
    while (left <= right)
    {
        int mid = left + ((right-left) >> 1);
        if (a[mid] < key)
            left = mid + 1;
        else if (a[mid] > key)
            right = mid - 1;
        else
            return mid;
    }
    return -1; // 返回-1表示未找到
}

int main()
{
    int a[8] = {1, 2, 4, 5, 6, 8, 11, 17}; // 下标从0开始
    int n = 8; // 数组元素数量
    int m = 8; // 查询次数
    int key; // 查询的元素
    while (m--)
    {
        cin >> key;
        cout << Binary_Search(a, n, key)+1 << endl; // 输出实际位置+1
    }
    return 0;
}
/*
1 // 查询1
1
2 // 查询2
2
4 // 查询4
3
5 // 查询5
4
6 // 查询6
5
8
6
11
7
17
8
*/
  • 查询数组元素位置从1开始返回0表示未找到
int Binary_search(int a[], int n, int x) // 数组下标从1开始
{
    int left = 1, right = n;
    while (left <= right)
    {
        int mid = (left+right) >> 1; // 二分
        if (a[mid] < x)
            left = mid + 1;
        else if (a[mid] > x)
            right = mid - 1;    
        else
            return mid; // 查询到返回元素索引(下标) 
    }
    return 0; // 返回0表示未找到
}
  • 二分搜索递归版本
int _Binary_Search(int a[], int left, int right, int key)
{
    if (left > right)
        return -1;
    int mid = (left + right) >> 1;
    if (a[mid] > key)
        return _Binary_Search(a, left, mid - 1, key);
    if (a[mid] < key)
        return _Binary_Search(a, mid + 1, right, key);
    return mid;
}

_Binary_Search(a, 1, n, key) // 调用

算法分析

时间复杂度是O(log n)

二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上:必须有序,我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序,可是又落到了第二个瓶颈上:它必须是数组。数组读取效率是O(1),可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。

二分查找除了找到排序数组中元素下标外,还有很多其他的应用,比如解方程近似值(偷懒不想写,下次补上)。关键是掌握二分这种思想!

  • 查找有序数组中第一个与key相等的元素
  • 查找有序数组中最后一个与key相等的元素
  • 查找数组中某个数出现的次数

解决以上三种问题关键在于理解二分边界left与right,以及判定符号<、>、<=、>=,自行体会。

跳出while (left <= right)循环条件是right < left,且left = right + 1。最后right和left一定是卡在”边界值”的左右两边。

  • 使用二分查询有序数组a中大于等于x的第一个数的位置(数组下标从1开始)
int Binary_search1(int a[], int n, int x)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return r + 1;
}
  • 使用二分查询有序数组a中小于等于x的最后一个数的位置(数组下标从1开始)
int Binary_search2(int a[], int n, int x)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] <= x)
            l = m + 1;
        else
            r = m - 1;
    }
    return l - 1;
}

补充

C++ STL 自带binary_search()二分查找以及sort()排序。但是请注意,binary_search() 用来在一个有序区间中使用二分法查找元素是否在这个区间中,它的返回值为bool,不是下标位置

int a[8] = {1, 7, 3, 5, 9, 6, 2, 4};
sort(a, a + 8); //首先排序
bool f = binary_search(a, a+n, key); // 然后使用二分查找
// 返回值为false表示未找到,为true表示找到

当然也可以自己写冒泡排序。

void Swap(int & a, int & b) // 交换两数
{
    int t = a;
    a = b;
    b = t;
}

void bubble_sort(int a[], int n) // 冒泡排序
{
    for (int i = 0; i < n-1; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] > a[j]) // 从小到大排序
                Swap(a[i], a[j]);
}
int a[8] = {1, 7, 3, 5, 9, 6, 2, 4};

bubble_sort(a, n); 

文中基础知识部分引自数据结构学习网,CSDN博客和博客园也有一些写的很好的文章,比如:二分查找法的实现和应用汇总你真的会写二分查找吗,推荐阅读:常用的STL查找算法

The end.
2017-11-24 星期五


更新

说明一下使用二分查找时查询大于小于某个值的第一个位置与最后一个位置的区别。

  • 代码
// 下标从1开始,找到第一个大于等于x的值的位置
int Binary_search1(int a[], int n, int x)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return r + 1;
}

// 下标从1开始,找到最后一个小于等于x的值的位置
int Binary_search2(int a[], int n, int x)
{
    int l = 1, r = n;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] <= x)
            l = m + 1;
        else
            r = m - 1;
    }
    return l - 1;
}

// 下标从0开始,找到第一个大于x的值的位置
int binary_Search1(int a[], int n, int val)
{
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] <= val)
            l = m + 1;
        else
            r = m - 1;
    }
    return r + 1;
}

// 下标从0开始,找到最后一个小于x的值的位置
int binary_Search2(int a[], int n, int val)
{
    int l = 0, r = n - 1;
    while (l <= r)
    {
        int m = (l+r) >> 1;
        if (a[m] < val)
            l = m + 1;
        else
            r = m - 1;
    }
    return l - 1;
}
  • 调用
int a[20] = {1, 2, 2, 2, 3, 5, 6, 7, 7, 7, 9, 9};
int b[20] = {0, 1, 2, 2, 2, 3, 5, 6, 7, 7, 7, 9, 9};
int x;
while (cin >> x)
{
    cout << "下标从0开始:" << endl;
    cout << binary_Search1(a, 12, x) << " " << binary_Search2(a, 12, x) << endl;
    cout << "下标从1开始:" << endl;
    cout << Binary_search2(b, 12, x) << " " << Binary_search1(b, 12, x) << endl;
}
  • 结果
1
1 -1
1 1
2
4 0
4 2
7
10 6
10 8
9
12 9
12 11

The end.
2017-12-05 星期二

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(七):线性表的查找之顺序查找与二分查找
  1. ZJing

    太傅 fucking great

    1. TaiFu_S
      @ZJing

      谢谢捧场哇!

  2. CongTsang

    欧巴桑好厉害哦,代码颜色换一下啊,狗眼瞎了

    1. TaiFu_S
      @CongTsang

      二哈换了换了doge5