二分法查找(折半查找)

平均时间复杂度:O(logN)

/**
 * create by Administrator
 * 2020-03-30
 */
package com.bj.zl.learn.find;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 二分法查找思路:
 * 1.首先确定该数组的中间下标
 * 2.然后让需要找的数和中间的数进行比较,大于中间数,则要查找的就是右边.
 * 3.当找到要找的数,或者左下标大于右下标的时候,结束查找.
 */
public class SearchTest {


    public static void main(String[] args) {

        int[] arr = {1,2,5,5,5,5,5,8,9};
        int findValue = 5;
       /* int i = binarySearch(arr, 0, arr.length-1, findValue);
        System.out.println(i);*/

       List<Integer> list = binarySearch2(arr,0,arr.length-1,findValue);
        System.out.println(list);
    }

    /**
     * 当数组有序时,切数组不重复的时候.
     * @param arr
     * @param left
     * @param right
     * @param findval
     * @return
     */
    private  static int binarySearch(int[] arr,int left,int right,int findval){


        if (left>right){
            return -1;
        }
        int mid = (left+right)/2;
        int midValue = arr[mid];

        if (findval > midValue){
            return binarySearch(arr,mid+1,right,findval);
        }else if (findval < midValue){
            return binarySearch(arr,left,mid-1,findval);
        }else {
            return mid;
        }
    }

    /**
     * 返回一个数组下标范围
     * @param arr
     * @param left
     * @param right
     * @param findval
     * @return
     */
    private  static List<Integer> binarySearch2(int[] arr, int left, int right, int findval){

        if (left>right){
            return new ArrayList<>();
        }
        int mid = (left+right)/2;
        int midValue = arr[mid];

        if (findval > midValue){
            return binarySearch2(arr,mid+1,right,findval);
        }else if (findval < midValue){
            return binarySearch2(arr,left,mid-1,findval);
        }else {
            List<Integer> list = new ArrayList<>();
            int temp = mid-1;
            while (true){
                if (temp < 0 || arr[temp] != findval){
                   break;
                }
                list.add(temp--);
            }
            list.add(mid);
            temp = mid+1;
            while (true){
                if (temp > arr.length-1 || arr[temp] != findval){
                    break;
                }
                list.add(temp++);
            }
            return list;
        }
    }
}