二分查找的完善

• java

package Package01;

import java.util.ArrayList;
import java.util.List;



public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,8,10,89,1000,1234};

        ArrayList resIndex = binarySearch(arr,0,arr.length-1,1);

        System.out.println("resIdex=" + resIndex);

        }


    //二分查找算法
    

    public static ArrayList binarySearch(int[] arr, int left, int right, int findVal){
        if (left > right) {
            return new ArrayList();
        }

        int mid = (left+right)/2;
        int midVal = arr[mid];

        if(findVal > midVal){
            //向右递归
            return binarySearch(arr,mid+1,right,findVal);

        }else if(findVal < midVal){
            return binarySearch(arr,left,mid-1,findVal);
        }else{
            
//            return mid;
             ArrayList resIndexList = new ArrayList();

             //向mid的索引值的左边扫描
            int temp = mid-1;
            while(true){

                if(temp<0 || arr[temp]!=findVal){

                    //退出
                    break;
                }
                //否则，就temp放入集合中
                resIndexList.add(temp);
                temp -= 1;  //temp左移

            }
            resIndexList.add(mid);
            //向mid的索引值的右边扫描

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


        }

    }



    }