查找和选择

查找问题

线性查找

算法思想

最简单的查找算法。遍历一遍数组，如果找到目标，返回该目标的位置；否则返回 -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;
}

选择问题

最小值和最大值

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

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

Comments

▲