二分查找（附递归的二分查找方法）

二分查找是在一组排好序的数组里查找某个指定的元素。

例如查找元素7，则如下。

利用Scanner获取一个元素，在数组中查找，先找到数组的中间位置 middle =（left + right）/ 2; 如果所找的元素小于中间位置的元素，则在该中间位置的左边寻找，并且将middle-1(中间位置已经比过了)值赋给right,在求出左边元素的中间下标，直到找到该元素，右侧的原理相同。

优化middle：为了防止元素过多造成的left+right数据溢出，因此 middle = （right - lef + 1) / 2 + left; 为了提高效率还可以采用位移运算： middle = ((right - left + 1) >> 1) + left。

实现如下：

import java.util.Scanner;

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,5,7,10,15,20,28,56,79,85};
        Scanner sc = new Scanner(System.in);
        int val = sc.nextInt();
        int index = search(arr,val);
        System.out.println(index);
    }

    /**
     *
     * @param arr
     * @param val 要查找的数
     * @return 元素下标
     */
    private static int search(int[] arr, int val) {
        int right = arr.length - 1;
        int left = 0;
        while(left <= right) {
            int middle = (right + left) / 2;
            if (val == arr[middle]) {
                return middle;//找到则返回下标
            } else if (val < arr[middle]) {
                right = middle - 1;//要找得数比中间数小则在左边找
            } else {
                left = middle + 1;//要找得数比中间数小则在右边找
            }
        }
        return -1;
    }
}

附上二分查找的递归方法（自己调用自己）：

public class BinarySearchDemo {
    public static void main(String[] args) {
        int arr[] = {1,5,7,10,15,20,28,56,79,85};
        int index = binarySearch(arr,0,arr.length - 1,10);
        System.out.println(index);
    }

    /**
     *
     * @param arr
     * @param l 左下标
     * @param r 右下标
     * @param data  数据
     * @return
     */
    private static int binarySearch(int[] arr, int l, int r, int data) {
        int mid = (l + r) / 2;
        if(r < l){
            return -1;
        }
        if(arr[mid] == data){
            return mid;
        }
        if(arr[mid] < data){
            return binarySearch(arr,mid+1,r,data);
        }else{
            return binarySearch(arr,l,mid-1,data);
        }
    }
}

二分查找（附递归的二分查找方法）

推荐阅读