二分查找（Java实现）

二分查找的实现方法：

（1）使用API：Arrays类的binarySearch方法

（2）迭代方式

（3）递归方式

方法一：Arrays类的binarySearch方法

public static void main(String[] args) {
        int[] arr = {1, 10, 23, 35, 55, 66, 88};
        //二分查找
        int index1 = Arrays.binarySearch(arr,66);
        int index2 = Arrays.binarySearch(arr,18);
        //如果需要查找的数据存在，就返回数组中对应数据的下标值，
        // 如果不存在，返回值为：   -（应该插入的位置索引+1）
        System.out.println(index1);   
        System.out.println(index2);    
    }

输出结果：5 -3
需要注意：如果需要查找的数据存在，就返回数组中对应数据的下标值，

如果不存在，返回值为： -（应该插入的位置索引+1）

方法二：迭代方式

package 二分查找.方法二_迭代方式;

public class Method02 {
    public static void main(String[] args) {
        //定义一个数组
        int[] arr = {10,14,16,25,28,30,35,88,100};
        int index = binarySearch(arr, 100);
        System.out.println(index);

    }

    /**
     *
     * @param arr 已排序的数组
     * @param data 要找的数据
     * @return 索引，如果元素不存在，直接返回-1
     */
    public static int binarySearch(int[] arr,int data){
        int low = 0;
        int high = arr.length - 1;
        while(low <= high){
//            int mid = (low + high)/2;
            int mid = (low + high) >>> 1;//正数右移运算相当于除以二
            if(arr[mid]< data){
                low = mid+1;
            } else if (arr[mid] > data) {
                high = mid - 1;
            }else if(arr[mid] == data){
                return mid;
            }
        }
        return -1;
    }
}

输出结果：8

方法三：递归方法

package 二分查找.方法三_递归方法;

public class Method03 {
    public static void main(String[] args) {
        int[] arr = {10,14,16,25,28,30,35,88,100,101};
        int index = binarySearch(arr,16,0, arr.length-1);
        System.out.println(index);
    }

    /**
     *
     * @param arr 已排序的数组
     * @param data 要找的数据
     * @param low 左侧初始位置规定为0
     * @param high 右侧初始位置规定为数组长度-1
     * @return 索引，如果元素不存在，直接返回-1
     */
    public static int binarySearch(int[] arr,int data,int low,int high){
        if(low > high)
            return -1;
//        int mid = (low+high)/2;
        int mid = (low+high)>>>1;
        if(arr[mid] == data)
            return mid;
        else if (arr[mid] > data)
            return binarySearch(arr,data,low,mid-1);
        else
            return binarySearch(arr, data, mid+1, high);


    }
}

输出结果：2

以上部分对大部分数组来说的，已经可以满足要求了，但是还可能会遇到边界值问题，这里我说一下：

边界值问题：

假设我们有一个有序数组{10,14,16,16,16,16,16,88,100}，数组中出现了多个大小相同的数据16，这些相同数据的最右边的元素，即index值最大的为上边界，索引为6,；这些相同数据的最左边元素，即index值最小的为下边界，索引为2；传入需要查找的数据16，在数组中可以找到就返回索引，找不到就返回-1。那么这样的数组我们应该如何取得上边界和下边界索引值呢？

求上边界

public static void main(String[] args) {
        int[] arr = {10,14,16,16,16,16,16,88,100};
        int index2 =upperBinarySearch(arr,16);
        System.out.println(index2);
    }

    public  static int upperBinarySearch(int[] arr,int data){
        int low = 0;
        int height = arr.length;
        int item = -1;
        while (low < height){
            int mid = (low + height)/2;
            if (data == arr[mid]){
                item = mid;
                low = mid+1;
            }else if (data < arr[mid]){
                height = mid;
            }else if (data > arr[mid]){
                low = mid + 1;
            }
        }
        return item;
    }

输出结果：6

求下边界

public static void main(String[] args) {
        int[] arr = {10,14,16,16,16,16,16,88,100};
        int index1 =lowerBinarySearch(arr,16);
        System.out.println(index1);
    }

    public  static int lowerBinarySearch(int[] arr,int data){
        int low = 0;
        int height = arr.length;
        int item = -1;
        while (low < height){
            int mid = (low + height)/2;
            if (data == arr[mid]){
                item = mid;
                height = mid;
            }else if (data < arr[mid]){
                height = mid;
            }else if (data > arr[mid]){
                low = mid + 1;
            }
        }
        return item;
    }