二分查找

import java.util.ArrayList;

/**
 * @author klr
 * @create 2020-07-14-12:26
 */
public class BinarySearch {


    public static void main(String[] args) {
        int[] arr = new int[]{11, 66, 22, 44,44,44,44, 99};
        System.out.println(BinarySearch.search1(arr, 0, arr.length - 1, 44).toString());
    }


    public static int search(int[] arr, int left, int right, int findVal){

        //如果找不到这个数，要给个出口
        if (left > right) {
            return -1;
        }

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

    //可查找所有的下标
    public static ArrayList<Integer> search1(int[] arr, int left, int right, int findVal){

        //如果找不到这个数，要给个出口
        if (left > right) {
            return new ArrayList<>();
        }

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

            ArrayList<Integer> integers = new ArrayList<>();
            int temp=mid-1;
            while (temp >= 0 && arr[temp] == midVal) {
                integers.add(temp);
                temp--;
            }
            integers.add(mid);
            temp=mid+1;
            while (temp <= arr.length - 1 && arr[temp] == midVal) {
                integers.add(temp);
                temp++;
            }
            return integers;
        }
    }
}