二分查找

一、二分查找核心

1）二分查找的原理

二分查找(Binary search)也称折半查找，是一种效率较高的查找方法。

1.  设置查找区间：low = 0；high= n；
2. 若low > high时仍未找到，则查找失败；否则转步骤3
3. 取中间位mid = (low + high) / 2；比较 target 与 arr[mid]
4. 若 target < arr[mid]，则high = mid - 1；查找在左半区间进行，转步骤2
5. 若 target > arr[mid]，则low = mid + 1；查找在右半区间进行，转步骤2
6. 若 target = arr[mid]，则查找成功，返回 mid 值

2）二分查找需要满足以下条件

1. 要求线性表中的记录必须按关键码有序
2. 链表必须按顺序存储

3）简单示例

从一个数列中找到数字37

通过二分查找与顺序查找演示对比，可以看出 二分查找 在查找数字 37 时只需3次，而 顺序查找 在查找37时需要12次

4）时间复杂度

二分查找最好时间复杂度是：最好情况下只需要进行1次比较就能找到目标元素

二分查找最坏时间复杂度是：最坏情况就是查找不到目标元素

二分查找平均时间复杂度是

二、代码

1）非递归写法

    public int BinarySearch(int[] arr, int len, int target) {
        int low = 0;
        int high = len;
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (target < arr[mid]) high = mid - 1;
            else if (target > arr[mid]) low = mid + 1;
            else return mid;
        }
        return -1;
    }

2）递归写法

    public int BinarySearch(int[] arr, int low, int high, int target) {
        if (low > high) {
            return -1;
        } else {
            int mid = (low + high) / 2;
            if (target < arr[mid]) return BinarySearch(arr, low, mid - 1, target);
            else if (target > arr[mid]) return BinarySearch(arr, mid + 1, high, target);
            else return mid;
        }
    }