算法图解之二分查找

阅读这篇文章就证明你已经开始踏上了算法的修仙之路，接下来我会两天一更，介绍图解算法里面的算法的实现, 适合Java程序员阅读。

文章目录

• 前言
• 一、使用工具
• 二、分析简单和二分查找的优缺点
• 三、算法实现
• • 一. 分析算法
  • 二. 算法实现
• 四、思考一下这个问题
• • 一. 题目
  • 二. 答案
  • 三. 解析

---

前言

提示：这里可以添加本文要记录的大概内容：

例如：这里可能需要一些数学基础, 比如对数函数和一次函数, 都很简单百度百科可以去查一下他们的运算法则

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、使用工具

记笔记：用Typora, 个人觉得做笔记用这个够用了，一定要学会的技能
写代码：idea 社区版 或者其他也行，不影响学习算法

二、分析简单和二分查找的优缺点

图示:
1.简单查找

2.二分查找

三、算法实现 一. 分析算法

我们可以把算法联想到生活中的各个游戏中去，
这样会很轻松, 
比如二分查找更像猜数字，
1~100个数字中让你猜一个数字，
你不可能从1到100依次猜过去吧, 肯定会从中间猜,然后缩小范围，
这就是二分查找的核心思想

二. 算法实现

二分查找算法的实现

/**
 * 二分查找  -> 最多查询次数 以二为底的log函数
 *  1.优点:
 *      效率较高, 减少了运行时间,但是也占用了一些空间, 但总体效率高
 *  2.缺点:
 *      占用的空间较高, 数据必须有序,否则无法执行
 *  3.什么时候用：
 *      查询的数据必须有序, 这是前提
 *  4.例子: my_list = [1,3,5,7,9] -> 查找6, 9
 */
public class binary_search {

    public static void main(String[] args){

        //创建一个数组  -> 准备数据
        Integer[] my_list = new Integer[]{1,3,5,7,9};
        System.out.println("测试 = " + my_list[0]);

        //查找item -> 创造函数
        Integer item1 = findItemByBinarySearch(my_list,6);
        Integer item2 = findItemByBinarySearch(my_list,9);

        //找出他在数组中的索引
        System.out.println("索引的位置 = " + item1);
        System.out.println("索引的位置 = " + item2);
    }

    // binary_search=二分查找方法的实现   有点类似于猜数字的小游戏
    private static Integer findItemByBinarySearch(Integer[] my_list, int i) {
        //起始位置
        Integer low = 0;
        //最末位置
        Integer high = my_list.length - 1;

        Integer mid;
        Integer item;

        while(low <= high){
            //实打实的除, 向下取整
            mid = (low + high) / 2;
            //获得中间的值
            item = my_list[mid];
            if(i == item){
                return mid;    //返回索引的位置
            }
            if(i > item){
                low = mid + 1;    //大于中间位置的, 缩小到mid+1 ~ high
            }else{
                high = mid - 1;  //小于中间位置的, 缩小到low ~ mid -1 
            }
        }
        return null;     //当low > high 的时候就是没找到, 返回为null
    }
}

结果

四、思考一下这个问题 一. 题目

如果数组中一共有128个数据, 请问用二分查找，最多有多少步可以查找到?
结合之前二分查找的大O运行时间为 log2(n)

下面会有我给的答案

二. 答案

最多走7个步骤 

下面我会给出解析

三. 解析

手写算出来

代码跑出来

这个需要128个数据有点难找, 其实我们可以从2的倍数下手, 比如4，8等数字,
这个大家可以自己动动手实现一下

代码示例: