查找（Search）：是在一个数据集合中查找满足给定条件的记录。对于查找问题来说，没有一种算法对于任何情况下都是合适的。

查找表（Search Table）：是由同一类型的数据元素（或记录）构成的集合。对查找表经常进行的操作：

  1. 查询某个数据元素是否在查找表中**（静态查找表）**
  2. 检索某个数据元素的属性**（静态查找表）**
  3. 向查找表中添加一个数据元素**（动态查找表）**
  4. 向查找表中删除一个数据元素**（动态查找表）**

顺序查找算法

顺序查找：又称顺序搜索算法或者线性搜索算法，是所有查找算法中最基本、最简单的。

基本思想：从查找表的一端开始，顺序扫描线性表，逐个同记录的关键字作比较，如果匹配成功，则查找成功；反之，直到最后一个关键字都没有匹配成功，则为失败。

  • 时间复杂度=O(n)，空间复杂度=O(1)；最好时间复杂度为O(1)；
  • 适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。
  • 静态查找表既可以使用顺序表表示，也可以使用链表结构表示。
  • 优点：算法简单而且使用面广。
  • 缺点：查找效率较低，特别是当待查找集合中元素较多时，不推荐使用顺序查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = new int[] { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
        int index = linear_search(arr, 33);
        if (index != -1)
        {
            Console.WriteLine($"查找成功！序列为第{index + 1}个元素");
        }
        else
        {
            Console.WriteLine("查找失败");
        }
    }

    private static int linear_search(int[] arr, int value)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] == value)
            {
                return i;
            }
        }
        return -1;
    }
}

输出：

查找成功！序列为第7个元素

二分查找算法

二分查找：又称折半查找、二分搜索、折半搜索等，是在分治算法基础上设计出来的查找算法。

基本思想：将表中间位置记录的关键字与查找关键字比较，若相等，则查找成功；否则利用中间位置记录将表分为前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

  • 时间复杂度=O(log2n)，循环方式：空间复杂度=O(1)，递归方式：时间复杂度=O(log2n)
  • 数组元素必须有序，查找的数值不能多个，只能一个。必须采用顺序存储结构。
  • 优点：比较次数少，查找速度块，平均性能好。
  • 缺点：必须要求待查表为有序表；插入删除困难。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = new int[] { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
        //int index = binary_search1(arr, 0, 9, 31);
        int index = binary_search2(arr, 0, 9, 31);
        if (index != -1)
        {
            Console.WriteLine($"查找成功！序列为第{index + 1}个元素");
        }
        else
        {
            Console.WriteLine("查找失败");
        }
    }

    // 递归
    private static int binary_search1(int[] arr, int start, int end, int value)
    {
        if (start > end) return -1;

        int mid = start + (end - start) / 2;
        if (value == arr[mid])
        {
            return mid;
        }
        if (value < arr[mid])
        {
            return binary_search1(arr, start, mid - 1, value);
        }
        else
        {
            return binary_search1(arr, mid + 1, end, value);
        }
    }

    // 非递归
    private static int binary_search2(int[] arr, int start, int end, int value)
    {
        int left = start;
        int right = end;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] == value)
            {
                return mid;
            }
            else if (value < arr[mid])
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return -1;
    }
}

输出：

查找成功！序列为第6个元素

插值查找算法

插值查找：又称为插值搜索算法，是在二分查找算法的基础上改进的一种查找算法，将查找点的选择改进位自适应选择，提高查找效率。

基本思想：插值查找类似平时我们查字典的时候，查一个以 s 开头的单词时，绝对不会用二分查找，从字典的中间第一页开始，因为我们知道它的大概位置是在字典的较后面部分，所以可以从后面的某处查起。我们先从首字母 s 的地方开始查找，然后再根据第二个字母在字母表中的位置，找到对应位置再继续查找，这样重复这个过程，直到找到我们查找的这个单词这就是插值查找的基本思想

  • 顺序存储的有序数列，根据关键字在数据中均匀分布。
  • 比较元素的位置公式：

$$
Mid = Begin + ( (End - Begin) / (A[End] - A[Begin]) ) * (X - A[Begin])
$$

  • Mid：计算得出的元素的位置；
  • End：搜索区域内最后一个元素所在的位置；
  • Begin：搜索区域内第一个元素所在的位置；
  • X：要查找的目标元素；
  • A[]：表示整个待搜索序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int index = interpolation_search(arr, 0, 9, 5);
        if (index != -1)
        {
            Console.WriteLine($"查找成功！序列为第{index + 1}个元素");
        }
        else
        {
            Console.WriteLine("查找失败");
        }
    }
    
    private static int interpolation_search(int[] arr, int begin, int end, int value)
    {
        if (begin > end)
        {
            return -1;
        }
        // 如果查找表中只有一个元素，则比较该元素和待查元素的值
        if (begin == end)
        {
            return arr[begin] == value ? begin : -1;
        }

        // 根据公式找到中间元素的所在位置
        int mid = ((end - begin) / (arr[end] - arr[begin]) * (value - arr[begin]));

        // 递归出口
        if (value == arr[mid])
        {
            return mid;
        }

        // 递归查询
        if (value < arr[mid])
        {
            return interpolation_search(arr, begin, mid - 1, value);
        }
        else
        {
            return interpolation_search(arr, mid + 1, end, value);
        }
    }
}

输出：

查找成功！序列为第5个元素

哈希查找算法

哈希查找：又称散列查找算法，是一种借助哈希表（散列表）查找目标元素的方法，查找效率最高时对应的时间复杂度位O(2)。

哈希表：又称散列表，是一种存储结构，通常用来存储多个元素。和其它存储结构（线性表、树等）相比，哈希表查找目标元素的效率非常高。每个存储到哈希表中的元素，都配有一个唯一的标识（又称“索引”或者“键”），用户想查找哪个元素，凭借该元素对应的标识就可以直接找到它，无需遍历整个哈希表。

  • 适用于大多数场景，既支持有序序列，也支持无序序列。
  • 常见的散列函数：直接定址法，除留余数法，平方取余法等
  • 处理冲突的方法：开放定址法，线性探测法，拉链法等
  • 影响冲突的主要三个因素：
    • 散列函数是否均匀
    • 处理冲突的方法
    • 散列表的装填因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = new int[] { 5, 30, 20, 55, 50 };
        int[] hashArr = new int[10];
        CreateHash(arr, hashArr);
        int index = hash_search(hashArr, 20);
        if (index != -1)
        {
            Console.WriteLine($"查找成功！序列为第{index + 1}个元素");
        }
        else
        {
            Console.WriteLine("查找失败");
        }
    }

    // 哈希函数
    private static int hash(int value)
    {
        return value % 10;
    }

    // 创建哈希表
    private static void CreateHash(int[] arr, int[] hashArr)
    {
        int i, index;
        for (i = 0; i < arr.Length; i++)
        {
            // 通过哈希函数计算当前元素在哈希表中的位置
            index = hash(arr[i]);
            while (hashArr[index] != 0)
            {
                index++;
            }
            hashArr[index] = arr[i];
        }
    }

    private static int hash_search(int[] hashArr, int value)
    {
        // 通过哈希函数计算得到待查元素的下标
        int hashIndex = hash(value);
        // 如果发生冲突，则使用线性探测法向后探测
        while (hashArr[hashIndex] != value)
        {
            hashIndex = (hashIndex + 1) % 10;
            // 如果探测位置为空
            if (hashArr[hashIndex] == 0 || hashIndex == hash(value))
            {
                return -1;
            }
        }
        return hashIndex;
    }
}

输出：

查找成功！序列为第2个元素