1.概述

二分查找是针对有序数列的，对无序数列是无效的，在有序序列中使用二分查找能大大提高查找效率。

以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。

2.代码实现

二分查找非递归

public class BinarySearchNoRecur {
    public static void main(String[] args) {
        // 测试
        int[] arr = {1, 3, 8, 10, 11, 67, 100};
        int index = binarySearch(arr, 11);
        System.out.println("index=" + index);//
    }

    /*
     * @param arr: arr是升序排列
     * @param target:
     * @return: int
     * @return: -1 表示没查找到
     * @description:二分查找非递归实现
     */
    public static int binarySearch(int arr[], int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) { // 要继续查找
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1; // 需要向左边查找
            } else {
                left = mid + 1; // 需要向右边查找
            }
        }
        return -1;
    }
}

二分查找非递归实现

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,102,222};
        int i = binarySearch(arr,0,arr.length-1, 222);
        System.out.println("下标为:"+i);

    }
    /*
     * @param arr: 传入的数组
     * @param left: 数组左边的索引
     * @param right: 数组右边的索引
     * @param v: 要查找的值
     * @return: int
     * @description: 二分查找必须传入一个有序的数组
     */
    public static int binarySearch(int arr[],int left,int right,int findV){
        int mid = (left + right) / 2; //中间的索引
        int midV = arr[mid];
        if (left > right){
            return -1;
        }
        if (findV > midV){ //向右递归
          return   binarySearch(arr,mid+1,right,findV);
        }
        if (findV < midV){
            return binarySearch(arr,left,mid-1,findV);
        }
        else
            return mid;
    }
}

简单完善

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,10,10,10,10,89,102,222};
        ArrayList integers = binarySearch(arr, 0, arr.length - 1, 10);
        System.out.println("下标为:"+integers);

    }
    /*
     * @param arr: 传入的数组
     * @param left: 数组左边的索引
     * @param right: 数组右边的索引
     * @param v: 要查找的值
     * @return: int
     * @description: 二分查找必须传入一个有序的数组
     */
    public static ArrayList binarySearch(int arr[],int left,int right,int findV){
        int mid = (left + right) / 2; //中间的索引
        int midV = arr[mid];
        if (left > right){  //没有找到结束递归
            return new ArrayList<>();
        }
        if (findV > midV){ //向右递归
            return   binarySearch(arr,mid+1,right,findV);
        }
        if (findV < midV){
            return binarySearch(arr,left,mid-1,findV);
        }
        else {
            /*
             *1.在找到mid后不要马上返回
             *2.继续向左或向右扫描 找到满足的下标 加入到集合
             *3.返回集合
             * @description:
             */
            ArrayList index = new ArrayList<>();
            int temp = mid - 1;
            while (true){
                if (temp < 0 || arr[temp] !=findV){
                    break;
                }
                //否则 将下标放入index
                index.add(temp);
                temp--;
            }
            index.add(mid);
            temp = mid + 1;
            while (true){
                if (temp > right || arr[temp] !=findV){
                    break;
                }
                //否则 将下标放入index
                index.add(temp);
                temp++;
            }
            return index;
        }
    }
}