顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析：

　 查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时，需要n+1次比较，时间复杂度为O(n);

所以，顺序查找的时间复杂度为O(n)。

代码实现

以 c++ 代码为例：

  [c]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
** 顺序查询算法
** @param arr 数组信息
** @param target 目标值
** @param arrLength 数组长度
*/
int sequeneceSearch(int arr[], int target, int arrLength) {
    int i;
    for(i = 0; i < arrLength; i++) {
        if(target == arr[i]) {
            return i;
        }
    }
    return -1;
}

二分查找法

二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）[1]、对数搜索（英语：logarithmic search）[2]，是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

概览

分类 搜索算法
数据结构 数组
最坏时间复杂度 O(log(n))
最优时间复杂度 O(1)
平均时间复杂度 O(log(n))
空间复杂度 迭代: O(1); 递归: O(log(n))

步骤

① 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2

② 用待查关键字值与中间位置的关键字值进行比较；

　 若相等，则查找成功

　 若大于，则在后（右）半个区域继续进行折半查找

　 若小于，则在前（左）半个区域继续进行折半查找

③ 对确定的缩小区域再按折半公式，重复上述步骤。

最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。

Java 代码实现

  • 循环
  [java]
1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearch(int[] arr, int start, int end, int hkey){
    if (start > end)
        return -1;

    int mid = start + (end - start)/2;    //防止溢位
    if (arr[mid] > hkey)
        return binarySearch(arr, start, mid - 1, hkey);
    if (arr[mid] < hkey)
        return binarySearch(arr, mid + 1, end, hkey);
    return mid;  

}
  • 递归
  [java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch(int[] arr, int start, int end, int hkey){
    int result = -1;

    while (start <= end){
        int mid = start + (end - start)/2;    //防止溢位
        if (arr[mid] > hkey)
            end = mid - 1;
        else if (arr[mid] < hkey)
            start = mid + 1;
        else {
            result = mid ;  
            break;
        }
    }

    return result;
}

参考资料

  • 顺序查找

https://www.cnblogs.com/yw09041432/p/5908444.html

https://www.jb51.net/article/53863.htm

https://blog.csdn.net/jiandanokok/article/details/50517837

  • 二分查找

二分搜索算法

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html