二分查找

# 引入

## 从大家熟悉的猜数字游戏

游戏规则：随机给出一个数字 并给出范围，让其 一直猜，每次根据猜的大小给出提示

小了还大了，直到找到这个数字。

1 简单查找

从1 开始 依次增加 假如所给的数字是10000 那么这个时间是很长的，

也就是我们算法中所说的 o (n)  那么如何简化这种方法，这时我们想

所给的提示。

2 分范围查找

我们先给出一个范围 1 ~ 100 我们不妨直接从50开始，然后跟据判断就可以缩小一半的范围，

类似于检查电路。

事实上我们并不一定要 每次选区中间

举个简单的例子 1 ~ 100 我们随机给出的数字为1 我们采用二分 法

50|大

--|--

25|大

12|大

6|大

3|大

2|大

1|找到了

这里所举得就是最差的例子 用了7次 ，也就是说 在最复杂的情况下 也才7次。

假如我们按照1:99的比例去分 直接第一个就选2这样只需要两次就能找到。但是如果去找99这个数字会变为一个 简单查找的次数。

# 为什么是二分

这里就牵扯到一个平均复杂度的问题，就像上面的例子二分的最差情况 要好于其他分发，其实计算机的二进制也有点这个的意思。

# 复杂度

前面提到了简单查找的复杂的是0 (n) 那么二分是多少呢。 这就用到大家所学的对数了，一个数能除以几次2 也就是log2n 这就是最后要寻找的次数。随着数据规模的增大会有很大的差别

实际上在算法中经常提到log 一般都是以2为底 至于原因 跟为什么是二分异曲同工。

# java代码

对于奇数 和 偶数的问题 因为是整除 所以不需要担心这个问题

```java

public int binary_search(int[] arr, int result){

        int low = 0 , high = arr.length - 1;

        int mid;

        while(low <= high){

            mid = low + (high - low) / 2;

            int guess = arr[mid];

            if (guess == result)

                return mid;

//            说明找到了位置。

            if (guess > result){

//                猜的大了 那么应该舍去一般 取前半部分 high的位置发生改变

                high = mid - 1;

            }else

                low = mid + 1;

        }

//        while 循环结束 说明没有找到

        return -1;

    }

```

## 值得大家注意的是 二分之所以能分是因为顺序已知所以一般用于排好序的数据

## 最后，后续会持续更新算法博客 。 顺序参考算法图解适合新手入门。