Java 二分查找

前言：

    二分查找又称折半查找，是一种效率较高的查找方法。前提条件：列表为有序 ， 时间复杂度：o(logn)。

算法原理：

<1>首先确定为查找区间的中间位置mid = (end - start) / 2 + start；
<2>比较中间位置与目标元素的值：
  1)若相等，则查找成功，返回结束；
  2)若中间位置元素大于目标值，则在中间位置左半部分查找；
  3)若中间位置元素小于目标值，则在中间位置右半部分查找；
<3>重复上述步骤。

算法实现：

/**
 * @author lm
 * @create 2018-10-13 13:11
 * @desc 折半查找算法 
 **/
public class BinarySearch {
    /**
     * 折半查找算法
     *
     * @param arr    有序数组
     * @param start  数组起始 查找位置
     * @param end    数组结束查找位置
     * @param target 目标元素
     * @return -1：查找失败 非-1: 元素所在位置
     */
    public static int binarySearch(int[] arr, int start, int end, int target) {
        if (start >= end) {
            return -1;
        }
        int mid = (end - start) / 2 + start;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            end = mid - 1;
            return binarySearch(arr, start, end, target);
        } else {
            start = mid + 1;
            return binarySearch(arr, start, end, target);
        }
    }

    //测试用例
    public static void main(String[] args) {
        int[] arr = {0,1,2,3,4,5,6,7,8,9,10};
        int res = binarySearch(arr,0, arr.length, 5);
        System.out.println(res);
    }
}

算法分析：

<1>由于每次折半查找，因此查找次数比较少，查找速度相对较快，平均性能比较好；
<2>由于要求带查找列表为有序，因此该算法适用于元素不经常变动而查找频繁的场景。