数据结构与算法（十五） 二分查找算法

二分查找算法

二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空，则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半，其时间复杂度是O(logN)。

代码实现

 /**
     * 二分查找
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static int binarySearch(int [] arr ,int left,int right,int findVal){
        System.out.println("二分法查找");
        if (right<left){
            return -1;
        }
        int mid=(left+right)/2;

        if (arr[mid]>findVal){
            return  binarySearch(arr,left,mid-1,findVal);
        }else if (arr[mid]<findVal){
            return  binarySearch(arr,mid+1,right,findVal);
        }else {

            return mid;
        }
    }

二分法查找 可能有多个相同的值。

{1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.

代码实现

/**
     * 二分法查找 可能有多个相同的值
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */

    public static List<Integer> binarySearchMore(int [] arr,int left,int right,int findVal){

        if (right<left){
            return new ArrayList<>();
        }
        int mid=(left+right)/2;
        if (arr[mid]>findVal){
            return  binarySearchMore(arr,left,mid-1,findVal);
        }else if (arr[mid]<findVal){
            return  binarySearchMore(arr,mid+1,right,findVal);
        }else {

            List<Integer> indexList=new ArrayList<>();
            int temp=mid-1;
            while (true){
                if (temp<0 || arr[temp]!=findVal){
                    break;
                }
                indexList.add(temp--);
            }

            indexList.add(mid);

            temp=mid+1;

            while (true){
                if (temp>arr.length-1 || arr[temp]!=findVal){
                    break;
                }
                indexList.add(temp++);
            }
            return indexList;
        }

    }