分治算法（二分搜索）

每日一言 : 当我们真正热爱这世界时，我们才真正生活在这世上。——泰戈尔

二分搜索

什么是二分搜索

二分搜索又叫二分查找，是一种效率较高的查找方法，比如数据库的索引查找方式（哈希索引除外）就是一种二分、三分或者多分查找的算法，分的多少和索引结构有关。

要求线性表为有序表，并且要用向量作为表的存储结构，二分搜索的基本思想是先确定待查找记录所在的范围，然后逐步缩小范围，直到找到or找不到该记录位置。

二分查找的步骤如下

1. 先确定中间位置：middle=(left+right)/2
2. 将待查找的key值和data[middle].key值相比较，相等则查找成功并返回该位置，否则重新确定查找空间，继续二分查找，具体方法如下：
   • 如果data[middle].key大于key，由于data为有序线性表，可以知道data[middle->right].key全部都大于key，因此可以推断，若数据表中存在关键字符合的key，那么一定位于【left->middle】子表范围区间内
   • 反之亦然，data[middle].key 小于key，若数据表中存在关键字符合的key，那么一定位于【middle--》right 】子表范围区间内

java 实现如下

    public static void main(String[] args) {
        int [] array = {1,2,3,4,5,6,7,8,9};
        System.out.println(binary(array,0,array.length,5));
    }

    private static int binary(int [] data , int left ,int right ,int key) {
        // 获取中间位置， 一分为二
        int middle = (left + right) / 2;
        // 比较是否相等，相等返回当前位置，否则根据key的大小重新确立新的查找空间
        if (data[middle] == key) {
            return middle;
        }else if (data[middle] > key) {
            return binary(data , left, middle-1 ,key);
        }else {
            return binary(data , middle+1, right ,key);
        }
    }

附图

graph LR
A[有序线性表获取中位数] -- 查找值 --> B{中位数比较查找值}
B --大于or小于--> A
B --等于--> C(返回值)

简单通俗来说就是钱包，我们一般会习惯把钱进行一个整理排序，然后放入钱包中，从小到大依次存放，【1、2、5、10、20、50、100】，当我们买菜花了20，通过比较中位数5，花的钱大于中位，则在中位右侧区间，反之左侧

源码地址Github ，本文源自张建飞《代码精进之路:从码农到工匠》读后记录