Java实现二分查找BinarySearch算法_开发_开发者

1、实现原理

二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

如下是二分查找算法的查找过程，针对有序数组 int[] a={9,10,11,12,13,14,15}; ，low和high表示数组查找的区间，mid 表示查找区间的中间元素。

Java实现二分查找BinarySearch算法

2、代码实现

明白二分查找的原理，代码很容易明白了。如下代码Java实现

 /**
     * 简单二分查找
     * @param arr
    编程客栈 * @param value
     * @return
     */
    public static int bSeaarch(int[] arr,int value){
        int low=0;
        int high=arr.length-1;
        while (low<=high){
            int mid=low+((high-low)>>1);
            if (value==arr[mid]){
                return mid;
            }else if (value>arr[mid]){
                ljsow=mid+1;
            }else {
                high=mid-1;
            }
        }
        return -1;
    }

3、二分查找常见的变体

对于上面“值等于给定值”的二分查找在实际中用到的情况不多，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显，比如以下几种变体。

3.1、查找第一个值等于给定值的元素

数组 int[] a={9,10,12,12,12,13,15}; 中有重复的值，我们希望查找第一个等于 12的数据，也就是下标是 2 的元素。

 /**
     * 查找第一个值等于给定值的元素
     * @param arr
     * @param value
     * @return
     */
    public static int bSeaarch2(int[] arr,int value){
        int low=0;
        int high=arr.length-1js;
        while (low<=high){
            int mid=low+((high-low)>>1);
            //如果给定的值大于区间中间元素
            if (value>arr[mid]){
                low=mid+1;
            }else if (value<arr[mid]){  //如果给定的值大于区间中间元素
                high=mid-1;
            }else{  //如果给定的值等于区间中间元素
                //当前中间元素为第一个或者中间元素的前一个不等于给定值，则当前元素就是要查找第一个值
                if (mid==0||arr[mid-1]!=value){
                    return mid;
                }else {
                    high=mid-1;
                }
            }
        }
        return -1;
    }

3.2、查找最后一个值等于给定元素

数组 int[] a={9,10,12,12,12,13,15}; 中有重复的值，我们希望查找最后一个等于 12的数据，也就是下标是 4 的元素。

/**
     * 查找最后一个值等于给定元素
     * @param arr
     * @param value
     * @return
     */
    public static int bseaarch3(int[] arr,int value){
        int low=0;
        int high=arr.length-1;
        while (low<=high){
            int mid=low+((high-low)>>1);
            //如果跟定的值大于区间数组中间值，则 low=mid+1
            if (value>arr[mid]){
                low=mid+1;
            }else if (value<arr[mid]){  //如果跟js定的值小于区间数组中间值，则 high=mid-1
                high=mid-1;
            }else {
                //如果区间数组中间值是数组最后一个元素或者中间值的下一个元素不等于给定值，返回当前mid索引
                if ((mid==arr.length-1)||(arr[mid+1]!=value)) {
                    return mid;
                }else { //继续在下一区间查找
                    low=mid+1;
                }
            }
        }
        return -1;
    }

3.3、查找最后一个大于等于给定值的元素

数组 int[] a={9,10,12,13,14,15,16}; 中重复的值，我们希望查找最后一个大于等于12元素的索引，也就是下标是6 。

   /**
     * 查找第一个大于等于给定值的元素
      * @param arr
     * @param value
     * @return
     */
    public static int bsearch4(int[] arr,int value){
        int low=0;
        int high=arr.length-1;
        while (low<=high){
            int mid=low+((high-low)>>1);
            //如区间元素中间值大于等于给定元素
            if (arr[mid]>=value){
                // 如区间元素是数组第一个元素或者下一个元素小于给定值，则当前索引满足条件
                if (mid==0||arr[mid-1]<value){
                    return mid;
                }else { //不满足上面条件，继续循环
                    high=mid-1;
                }
            }else {
                low=mid+1;
            }
        }
         return -1;
    }

3.4、查找最后一个小于于等于给定值的元素

数组 int[] a={9,10,12,13,14,15,16}; 中重复的值，我们希望查找最后一个小于等于10元素的索引，也就是下标是0 。

/**
     * 查找最后一个小于于等于给定值的元素  `int[] a={9,10,12,13,14,15,16}
     * @param arr
     * @param value
     * @return
     */
    public static int bsearch6(int[] arr,int value){http://www.devze.com
        int low=0;
        int high=arr.length-1;
        while (low<=high){
            int mid=low+((high-low)>>1);
            if (arr[mid]>value){
               high=mid-1;
            }else {
                if ((mid==arr.length-1)||(arr[mid+1]>value)) {
                    return mid;
                }else {
                    low=mid+1;
                }
            }
        }
        return -1;
    }