查看“查找”的源代码

https://www.bilibili.com/video/BV1hg411V7Bm?p=65

=== 1）顺序查找 ===
顺序查找：将待查找的关键字跟表中的数据从头至尾按顺序进行比较。

平均查找长度（等概率情况）：
[[文件:平均查找长度.png|无|缩略图|600x600像素]]


=== 2）二分法查找 ===
二分法查找（折半查找）的基本思想是：（设R[low,...,high]是当前的查找区）

（1）确定该区间的中点位置：mid=⌊(low+high)/2⌋（向下取整）；

（2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下。

* 若R[mid].key>k，则由表的有序性可知R[mid,...,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,...,mid-1]中。因此，新的查找区间是左子表R[low,...,high]，其中high=mid-1。
* 若R[mid].key<k，则要查找的k必在mid的右子表R[mid+1,...,high]中，即新的查找区间是右子表R[low,...,high]，其中low=mid+1。
* 若R[mid].key=k，则查找成功，算法结束。

（3）下一次查找是针对新的查找区间进行，重复步骤（1）和（2）。

（4）在查找过程中，low逐步增加，而high逐步减少。如果high<low，则查找失败，算法结束。



请给出在含有12个元素的'''<big>有序表</big>'''{1，4，10，16，17，18，23，29，33，40，50，51}中二分查找关键字17的过程。
[[文件:二分查找.png|无|缩略图|600x600像素]]


折半查找在查找成功时关键字的比较次数最多为⌊log<sub>2</sub>n⌋+1次。

折半查找的时间复杂度为O(log<sub>2</sub>n)次。

折半查找仅适用于元素有序的顺序表。



=== 2）二分法查找（循环法） ===
<syntaxhighlight lang="c">
int biSearch(int r[], int low, int high, int key)
{
    //r[low...high]中的元素按非递减顺序排列，用二分查找法在数组r中查找与key相同的元素，若找到则返回该元素在数组r的下标，否则返回-1
    int mid;
    while(low <= high)
    {
        mid = (low + high)/2;
        if(key == r[mid]) return mid;
        else if (key < r[mid]) high = mid - 1;
        else low = mid + 1;

    }//end while
    return -1;

}//end biSearch
</syntaxhighlight>


https://www.bilibili.com/video/BV1hg411V7Bm?p=66

=== 2）二分法查找（递归法） ===
<syntaxhighlight lang="c">
int biSearch_rec(int r[], int low, int high, int key)
{
    //r[low...high]中的元素按非递减顺序排列，用二分查找法在数组r中查找与key相同的元素，若找到则返回该元素在数组r的下标，否则返回-1
    int mid;
    if(low <= high)
    {
        mid = (low + high)/2;
        if(key == r[mid]) return mid;
        else if (key < r[mid]) return biSearch_rec(r, low, mid-1, key);
        else return biSearch_rec(r, mid + 1, high, key);
    }//end if
    return -1;

}//end biSearch_rec
</syntaxhighlight>


=== 3）散列表查找：线性探查法 ===
散列表查找的基本思想是：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0..n-1](n<m)中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数。



关键码为（3，18，26，29，17），存储空间为10，散列函数h=key%7。取余结果相同就会发生冲突，发生冲突之后就往后面最近的一个空闲空间中。

比如存放17时：因为3%7=3，先放入了3的位置，17%7=3就只能往后放在后面最近的一个空闲空间6中了。
{| class="wikitable"
!地址空间
|0
|1
|2
|3
|4
|5
|6
|7
|8
|9
|-
!存储元素值
|
|29
|
|3
|18
|26
|17
|
|
|
|}



=== 3）散列表查找：拉链法 ===
关键码为（3，18，26，29，17），散列函数h=key%7，用链地址法。
[[文件:散列表查找 拉链法.png|无|缩略图]]


=== 考点1：二分法查找的条件 ===
在一个线性表上可以进行二分查找（折半查找）的充分必要条件是（）。

A、线性表采用顺序存储且元素有序排列  √

B、线性表采用顺序存储且元素无序排列

C、线性表采用单链表存储且元素有序排列

D、线性表采用单链表存储且元素无序排列


=== 考点2：二分法查找 ===
在有13个元素构成的有序表data[1..13]中，用折半查找（即二分查找，计算时向下取整）方式查找值等于data[8]的元素时，先后与（）等元素进行了比较。

A、data[7]、data[6]、data[8]

B、data[7]、data[8]

C、data[7]、data[10]、data[8]  √

D、data[7]、data[10]、data[9]、data[8]

解：

(1+13)/2=7

(8+13)/2=10

(8+9)/2=8


=== 考点3：散列表查找——线性探查法 ===
对于关键字序列（10，34，37，51，14，25，56，22，3），用线性查找法解决冲突构造哈希表，哈希函数为H(key)=key%11，关键字25存入哈希地址编号为（）。

A、2

B、3

C、5  √

D、6

解：
{| class="wikitable"
!0
!1
!2
!3
!4
!5
!6
!7
!8
!9
!10
|-
|
|34
|
|14
|37
|25
|
|51
|
|
|10
|}
10：10%11=10；

34：34%11=1；

37：37%11=4；

51：51%11=7；

14：14%11=3；

25：25%11=3；3已经有了，3后面最近的一个空位置是5，所以就放5



=== 考点4：散列表查找——链地址法 ===
对于关键码序列（54，34，5，14，50，36，47，83），用链地址法（或拉链法）解决冲突构造散列表（即将冲突的元素存储在同一个单链表中，单链表的头指针存入散列地址对应的单元），设散列函数为H(key)=key MOD 7（MOD表示整除取余运算），则构造散列表时冲突次数最多的哈希单元的地址是（）。

A、0

B、1

C、5  √

D、6

解：
{| class="wikitable"
!0
!1
!2
!3
!4
!5
!6
|-
|14
|50
|
|
|
|54
|34
|-
|
|36
|
|
|
|5
|83
|-
|
|
|
|
|
|47
|
|}
54：54%7=5；

34：34%7=6；

5：5%7=5；

14：14%7=0；

50：50%7=1；

36：36%7=1；

47：47%7=5；

83：83%7=6；



=== 总结 ===
顺序查找

* 链式存储或顺序存储都可以

二分法查找

* 顺序存储且元素有序
* 查找的方式

散列表查找

* 线性探查法（按照元素的值映射到区间冲突的处理方式）
* 拉链法/链地址法（按照元素的值映射到区间冲突的处理方式）