算法学习<1>---二分查找

引言

数据结构和算法对于程序员来说相当重要，我最近打算学习这一门课程，并以博客的形式记录自己的学习过程和心得，目前暂时从两本书入手，一本是《大话数据结构》，一本书《算法图解》，我先从《算法图解》，这本手开始学习吧~。如果你最近也在学习，可以关注一起学习，一起交流哦~

二分查找

先从一个问题思考，假设我们现在查找英语字典里的一K为开头的单词。如果我们从头开始翻，一直翻到K，那样太浪费时间了。通常我们都会直接翻开字典中间打开位置看看是什么字母的，如果我们翻到了J，K在J后面，那么我们继续往后翻就到了，比从头开始翻快多了。

二分查找是一种算法,其输入是一个有序的元素列表（必须有序）。如果要查找的元素包含在列表中，二分查找返回其位置，否则返回NULL。

再看一个简单的例子 如果我们现在在1到100里的数字找99，如果我们重头开始查找，需要99步 如果我们用二分查找，50->75->88->94->97->99，6次就能查找，而且在这个范围里任何数字在7次内都能查找完毕。简单查找：最多需要100步 二分查找：最多需要7步

当我们要查找的有240000元素的字典，使用二分查找，每次排除一般单词，最多只需18步。

一般而言，对于包含n个元素的列表，使用二分查找最多需要log2n步，而简单的查找需要n步。

C语言实现二分查找

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int target = 120;
int arr[10]={0,1,2,3,4,5,6,7,8,120};

int binary_search(int *p, int target, int len)
{
    int times;//记录查找次数
    int low,high,mid;
    low = 0;//最左边元素
    high = len - 1;//最右边元素
    mid = (low+high)/2;//中间元素
    while(low <= high){//循环执行直到只有一个元素
        times++;
        mid = (low+high)/2;
        if(target < arr[mid])
            high = mid - 1;
        else if(target > arr[mid])
            low = mid + 1;
        else if(target == arr[mid]){
            printf("times = %d\n",times);
            return mid;
        }


    }
    return -1;

}
int main()
{
    int res;
    int len = sizeof(arr)/sizeof(arr[0]);
    res = binary_search(arr,120,len);
    printf("The target at %d\n",res);
    return 0;
}

执行结果

程序执行查找4次，找到120在数组arr[9].

练习题

假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请 问最多需要几步才能找到？

log(2)128 = 7        7次

上面列表的长度翻倍后，最多需要几步？

8步

大O表示法

算法的运行时间以不同的速度增加

① 仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。② 大O表示算法的运行速度。它的单位不是秒，而是操作数。比如说简单查找一个含n个元素的列表，需要执行n次操作。而二分查找需要执行log（2）N次。

大O表示法指出在最糟糕的情况下的运行时间

简单查找的运行时间总是为O(n)。查找Adit时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

一些常见的大O运行时间

1. O(log n)，也叫对数时间，这样的算法包括二分查找。
2. O(n)，也叫线性时间，这样的算法包括简单查找。
3. O(n * log n)，这样的算法包括第4章将介绍的快速排序—— 一种速度较快的排序算法。
4. O(n2)，这样的算法包括第2章将介绍的选择排序—— 一种速度较慢的排序算法。
5. O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案—— 一种非常慢的算法。

小结

1. 二分查找的速度比简单查找快得多； 2. O(log n)比O(n)快。需要搜索的元素越多, 前者比后者就快得越多； 3. 算法运行时间并不以秒为单位； 4. 算法运行时间是从其增速的角度度量的； 5. 算法运行时间用大O表示法表示；