顺序查找

暴力遍历

  1. 顺序表

    通过数组下标递增来扫描每一个元素

  2. 链表

    通过next指针来扫描整个链表

二分查找（折半查找）(Binary Search)

流程图

代码实现

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
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define ElemType int

int Binary_Search(ElemType e, ElemType* arr, int n) {
	int low = 0, high = n - 1, mid;//记录数组下标
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (arr[mid] == e) {
			return mid;
		}
		else if (e < arr[mid]) {
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
}

int main() {
	int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int i = Binary_Search(7, arr, 10);
	printf("%d\n", i);
}

哈希查找（散列查找）(hash)

通过hash函数对要查找的内容进行转化成hash表的下标，然后，直接访问hash表，得到要找的内容or指针。

查找的时间复杂度为O(1)。

冲突