二分查找-递归(java)

 
 
 
import java.util.ArrayList;
 
 
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        int index = binarySearch(arr, 0, arr.length, -89);
        //-1
        System.out.println(index);
 
        int[] arr2 = {1, 8, 10, 89, 1000, 1000, 1000, 1234};
        ArrayList list = binarySearch2(arr2, 0, arr2.length, 1000);
        //[4, 5, 6]
        System.out.println(list);
    }
 
    /**
     * 二分查找算法
     *
     * @param arr     数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 要查找的值
     * @return 如果找到返回下标，如果没有找到，就返回-1
     */
    private static int binarySearch(int[] arr, int left, int right, int findVal) {
        if (right < left) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (midVal == findVal) {
            return mid;
        }
        if (midVal > findVal) {
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return binarySearch(arr, mid + 1, right, findVal);
        }
    }
 
    /**
     * 二分查找算法
     *
     * @param arr     数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 要查找的值
     * @return 如果找到返回下标集合，如果没有找到，就返回-1
     */
    private static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        if (right < left) {
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (midVal == findVal) {
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
 
            //    向左扫描
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }
                arrayList.add(temp);
                temp--;
            }
            arrayList.add(mid);
            //    向左扫描
            temp = mid + 1;
            while (true) {
                if (temp > arr.length || arr[temp] != findVal) {
                    break;
                }
                arrayList.add(temp);
                temp++;
            }
            return arrayList;
        }
        if (midVal > findVal) {
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            return binarySearch2(arr, mid + 1, right, findVal);
        }
    }
}