查找算法之二分查找算法

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

代码实现：

public class BinarySearchByRecursion {
    public static void main(String[] args) {
        int[] sortedArr = { 1, 3, 5, 8, 10, 12 };
        System.out.println(binarySearch(sortedArr, 10));
        System.out.println(binarySearchByRecursion(sortedArr, 0, sortedArr.length - 1, 10));
        //JDK提供二分查找算法
        System.out.println(Arrays.binarySearch(sortedArr, 10));
  
    }

    /**
     * 非递归二分查找算法
     * 
     * @param srcArray
     *            有序数组
     * @param des
     *            待查找数据
     * @return 返回-1 未找到
     */
    public static int binarySearch(int[] srcArray, int des) {

        int low = 0;// 第一个位置
        int high = srcArray.length - 1;// 最高位置.数组长度-1,因为下标是从0开始的
        while (low <= high) {// 循环终止条件是low不大于high
            // int middle = low + ((high - low) >> 1);
            int middle = (low + high) >> 1;// 左移1位=除2
            if (des == srcArray[middle]) {// 与最中间的数字进行判断,是否相等,相等的话就返回对应的数组下标
                return middle;
            } else if (des < srcArray[middle]) {
                // 移动high
                high = middle - 1;
            } else if (des > srcArray[middle]) {
                // 移动
                low = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 递归方式实现
     * 
     * @param srcArray
     * @param low
     * @param high
     * @param des
     * @return
     */
    public static int binarySearchByRecursion(int[] srcArray, int low, int high, int des) {

        if (low <= high) {
            int middle = (low + high) >> 1;
            if (des == srcArray[middle]) {// 与最中间的数字进行判断,是否相等,相等的话就返回对应的数组下标
                return middle;
            } else if (des < srcArray[middle]) {
                // 移动high
                return binarySearchByRecursion(srcArray, low, middle - 1, des);
            } else if (des > srcArray[middle]) {
                // 移动
                return binarySearchByRecursion(srcArray, middle + 1, high, des);
            }
        }
        return -1;
    }

}