二分查找

算法思想：要求要查找的序列有序，每次查找都是取序列中间的值与待查值进行比较，如果中间值比待查值大，则在序列前半部分继续循环查找，如果中间值比待查值小，则在序列后半部分继续循环查找。直到查到待查值为止，否则序列不存在待查的关键字。

Java实现：
非递归方式

package com.sam.example;

/**
 * 二分查找
 * 非迭代方式实现
 * 迭代方式实现
 */
public class BinarySearch {

    /**
     * 非迭代方式实现
     * @param arr
     * @param a
     * @return
     */

    public static int search(int arr[], int a) {
        int least = 0;
        int max = arr.length-1;
        int mid;

        while (least <= max) {
            mid = (least + max) / 2;
            if (a == arr[mid]) {
                return mid + 1;
            } else if (a > arr[mid]) {
                least = mid + 1;
            } else {
                max = mid - 1;
            }
        }

        return -1;
    }

    /**
     * 迭代方式实现
     * @param arr
     * @param least
     * @param max
     * @param a
     * @return
     */
    public static int searchViaInter(int arr[], int least, int max, int a) {

        if (least <= max) {
            int mid = (least + max) / 2;

            if (arr[mid] == a) {
                return mid + 1;
            } else if (arr[mid] > a) {
                return searchViaInter(arr, least, mid - 1, a);
            } else {
                return searchViaInter(arr, mid + 1, max, a);
            }
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,4,4,4,5};
        System.out.println(BinarySearch.search(arr, 1 ));
        System.out.println(BinarySearch.searchViaInter(arr, 0, arr.length-1, 1));
        System.out.println(BinarySearch.search(arr, 4 ));
        System.out.println(BinarySearch.searchViaInter(arr, 0, arr.length-1, 4));
        System.out.println(BinarySearch.search(arr, 5 ));
        System.out.println(BinarySearch.searchViaInter(arr, 0, arr.length-1, 5));
        System.out.println(BinarySearch.search(arr, 6 ));
        System.out.print(BinarySearch.searchViaInter(arr, 0, arr.length-1, 6));
    }
}