算法之旅—-二分查找

介绍二分查找

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

案例

随便想一个1-100的有序数组

你的目标是以最少的次数猜到这个数字，每次猜测后，会提示你小了，大了或对了。

假设你从1开始依次往上猜，这是简单查找，简单来说又叫傻找。每次猜测只能排除一个数字。

如果我给出的数字是100，你需要猜测100次，效率极低

更佳的查找方式

如果我们取中从50开始，提示大了，那将排除一半的数字。

使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半！

代码（Java）

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
28
29
30
31
32
33
34
35
36
37
38
public class BinarySearch {
    //一个按顺序的数组
    static int[] a = {1,2,3,4,5,6};
    public static void main(String[] args) {
        System.out.println(b(a,1));
    }
    //b方法，返回值object，传入数组和要查询的数
    public static Object b(int[] list,int item){

        //low和hight是查询范围
        int low = 0;
        int hight = a.length;

        //范围没缩小到只包含一个元素就一直循环
        while (low<=hight){
            //检查中间的元素
            int mid = (low+hight)/2;
            int guess = mid;

            //找到了元素
            if (guess==item){
                return mid;//直接返回找到的元素
            }

            //未找到元素
            if (guess>item){
                //查询的元素大了，将元素减少1，直到找到这个元素
                hight = mid -1;
            }else {
                //查询的元素小了，将元素加1，直到找到这个元素
                low = mid +1;
            }
        }
        //数组里没有要找的元素就返回none
        return "none";
    }
}