二分查找

发表于
字数统计: 639 | 阅读时长 ≈ 2

二分查找

​ 假设要在电话簿中找一个名字以K打头的人，可以从头开始翻页，知道进入以K打头的部分。但是你可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。

​ 又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。

​ 现在假设你登陆微信。当你这样做是，微信必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名名。如果你的用户名为wayne，微信可以从A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。

​ 这是一个查找问题，在上述所有情况下，都可以使用同一种算法来解决问题，这种算法就是二分查找。

二分查找

​ 二分查找是一种算法，其输入是一个有序元素列表。如果要查找元素是否包含在列表中，二分查找返回其位置；否则返回null。

​ 下面的实例说明了二分查找的工作原理。我随便想一个1~100的数字。

num1To100

​ 假设我现在想的数字是68

​ 那么：

​ 第一次猜 50，小了；

​ 第二次猜75， 大了；

​ 第三次猜63， 小了；

​ 第四次猜71， 大了；

​ 第五次猜67， 小了；

​ 第六次猜69， 大了；

​ 第七次猜68， 正确。

​ 每次查找，如果错误，你将排除一般的错误答案！

​ 但是如果从1开始猜，那么我们将猜68次才能猜到。

使用不同查找方法的最多步数

元素个数\查找方法 二分查找 简单查找
100 7 100
1024 10 1024

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 二分查找法
 * @param array   传入存放全部数据的容器
 * @param target  需要查找的目标数
 * @return
 */
public Integer searchDichotomy(Integer[] array, int target){
    int low =0;
    int hight=array.length-1;
    while(low<=hight){                 //遍历还没结束
        int mid = (low+hight)/2;       //取中间值mid点位置
        if(array[mid]==target){        //寻找到目标数
            return mid;
        }
        if(array[mid] > target){        //如果中间值大于目标数，则将highr点位置移动mid位置左边
           hight = mid-1;
        }
        if(array[mid] < target){       //如果中间值小于目标数，则将low点位置移动mid位置右边
            low = mid+1;
        }
    }
    return null;
}

运行时间

　　对数时间（或log时间）

　　　 100个数字最多猜7次 40亿猜32次

0%