# 二分查找算法（Algorithms）第一章

灰太狼 2022-06-13 09:51 156阅读 0赞

# 算法（Algorithms）第一章 #

## 2017.7.3 ##

配套资源网站：algs4.cs.princeton.edu。（如果你是初学者，不知道如何配置环境，如果你跟我遇到了相同的困难，在终端运行死活不成功，非常感谢这位博主给我提供了帮助：[算法第四版详细配置][Link 1]，文章是17年一月份写的，对我的帮助很大，博主是使用eclipse编译的，然后再使用命令行去运行。按照博主的项目结构就可以。也可以参考我的项目 分支chapter1里边的代码。） [我的GitHub地址][GitHub]：  
1. java基本数据类型有八种：（再巩固了一下！）  
\* 一个字节代表八位二进制数，也就是8位。  
\* 六个数字（byte（8位），short（16位），int（32位），long（64位），float（32位），double（64位）），  
\* 字符型char（16位，两个字节）  
\* 逻辑型Boolean（1位）  
2. 二分查找算法。  
二分查找算法是比较著名的、高效、应用广泛的。  
首先主要方法为下边的 indeOf 方法，需要两个参数  
1. 一个有序的int型数组  
2. 要查找的数字 也就是key值  
返回值有两种  
1. 如果返回-1 则说明没有当前要找的key  
2. 如果返回为>=0 的整数，则说明在数组中下标为该返回值  
普通实现方法如下：

public static int indexOf(int[] a, int key) {
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                // 被查找的键必定在 lo 到 hi 之间，或者是不存在.
                int mid = lo + (hi - lo) / 2;
                if      (key < a[mid]) hi = mid - 1;
                else if (key > a[mid]) lo = mid + 1;
                else return mid;
            }
            return -1;
        }
    public static void main(String[] args)
    {
         int[] whitelist = In.readInts(args[0]);
          Arrays.sort(whitelist);
         while (!StdIn.isEmpty())
               { // 读取键值，如果不存在于白名单中则将其打印
                  int key = StdIn.readInt();
                  if (rank(key, whitelist) < 0)
                  StdOut.println(key);
    }}

递归实现防范如下：

// 二分查找的递归实现
        public static int rank1(int key, int[] a)
        { 
            return rank(key, a, 0, a.length - 1); 
            }
        public static int rank(int key, int[] a, int lo, int hi)
        { //如果key存在于a[]中，它的索引不会小于lo且不会大于hi
             if (lo > hi) return -1;
             int mid = lo + (hi - lo) / 2;
             if (key < a[mid]) return rank(key, a, lo, mid - 1);
             else if (key > a[mid]) return rank(key, a, mid + 1, hi);
             else return mid;
        }

**原理：**

二分法超找就是取中间的值，来做比较，判断大小后缩小查找范围，一步一步采用递归实现查找出对应的下标，如果没有就跳出循环，返回-1.  
二分的核心就是一直不断的分成两份，来缩小范围。应用场景可以设定好白名单，然后可以查找出不在白名单里边的数据来过滤数据。例如银行账户通常是百万级别的，采用二分查找就会提高很大的效率！  
![原理图][SouthEast]

[Link 1]: http://www.cnblogs.com/kylinlin/p/6253362.html
[GitHub]: https://github.com/Stainlesswang/Alags4/wiki/Algorithms-4:-Chapter1
[SouthEast]: /images/20220613/bb41501d37a24160a5eda2aa5d22dd4c.png