一个装有 16 枚硬币的袋子，16 枚硬币中有一个是伪造的，伪造的硬币和普通硬币从表面上看不出有任何差别，但是那
个伪造的硬币比真的硬币要轻。现有给你一台天平，请你在尽可能最短的时间内找出那枚伪造的硬币

分治：
我们先将 16 枚硬币分为左右两个部分，各为 8 个硬币，分别称重，必然会有一半轻一半重，而我们要的就是轻的那组,重
的舍去。接下来我们继续对轻的进行五五分，直至每组剩下一枚或者两枚硬币，这时我们的问题自然就解决了

两部分组成
分（divide）：递归解决较小的问题
治（conquer）：然后从子问题的解构建原问题的解
三个步骤
1、分解（Divide）：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2、解决（Conquer）：若子问题规模较小而容易被解决则直接解决，否则递归地解各个子问题；
3、合并（Combine）：将各个子问题的解合并为原问题的解

#include "cstdio"
#include "cstdlib"


int BinarySearch(int *arr, int minSub, int maxSub, int num
) {
    if (minSub > maxSub) {
        return -1;//找不到 num 时,直接返回
    }
    int mid = (minSub + maxSub) / 2;
    if (num < arr[mid]) {
        return
                BinarySearch(arr, minSub, mid- 1, num);
    } else if (num > arr[mid]) {
        return
                BinarySearch(arr, mid + 1, maxSub, num);
    } else {
        return
                mid;//找到 num 时直接返回
    }
}

int main(void) {
    int arr[] = {1, 3, 7, 9, 11};
//    int index = BinarySearch(arr, 0, 4, 8);
    int index = BinarySearch(arr, 0, 4, 7);
    printf("index: %d\n", index);
    return 0;
}