查找问题

线性查找

算法思想

最简单的查找算法。遍历一遍数组,如果找到目标,返回该目标的位置;否则返回 -1。

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* linear_search - linear search an element from an array
* @param target the target element to be search
* @param array the array to be search from
* @param length the length of the array
*
* Linear search an element from an arary.
* @return the first index of the element.
* If the element does not exists in the array, returns -1.
*
*/
int linear_search(int target, int *array, int length)
{
int i;
for (i = 0; i < length; i++){
if (target == array[i])
return i;
}
return -1;
}

二分查找

算法思想

如果不是从一组随机的序列里查找,而是从一组排好序的序列里找出某个元素的位置,则可以有更快的算法:对于递增排序的序列,每次取出中间的元素,并与要查找的数比较。如果要查找的数大于该元素,则取右边一半的数,否则取左边一半的数。重复上述操作直到找到该数或者该元素的左侧和右侧已经没有元素。

C 语言实现

不依赖标准库的实现

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
/**
* binary_search - binary search an element from an array
* @param target the target element to be search
* @param array the array to be search from
* @param length the length of the array
*
* Binary search an element from an arary.
* @return the first index of the element.
* If the element does not exists in the array, returns -1.
*
*/
extern int binary_search(int target, int *array, int length)
{
int start = 0, end = length - 1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (target > array[mid])
start = mid + 1;
else if (target < array[mid])
end = mid - 1;
else
return mid;
log_info("mid: %d\tstart: %d\tend: %d",mid, start, end);
}
return -1;
}

直接调用标准库函数

直接调用标准库函数中的 bsearch,但该函数只会返回带查找的元素的值(如果序列中有该元素)或者NULL(如果序列中不存在该元素),而不会返回其位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
int array[8] = {1, 3, 5, 8, 10, 15, 20, 40};
int cmp_int(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int main(void)
{
int key = 15;
int *item;
item = bsearch(&key, array, 8, sizeof(int), cmp_int);
if (item != NULL)
printf("%d is in the array.\n", *item);
else
printf("%d isn't in the array.\n", *item);
return 0;
}

选择问题

最小值和最大值

期望为线性时间的选择算法

最坏情况为线性时间的选择算法