二分查找

如果懂了快速排序的话，对于理解二分查找就会更容易。同样也是左右指向不断的移动。先折半，然后左指向往后移动，右指向往前移，但是二分查找的前提必须是有序数组。下面演示代码：

//二分查找，前提是必需是有序数组
public class BinaryFind {

    public static void main(String[] args) {
        int[] arr = {1,32,654,874,3768,32132,32132,32132,32133};
        List<Integer> list = binaryFind(arr, 0, arr.length-1, 32132);
        System.out.println(list);
    }
    
    public static List<Integer> binaryFind(int[] arr,int left,int right,int findVal){
        if(left>right || findVal<arr[0] || findVal>arr[arr.length-1]) {
            return new ArrayList<Integer>();
        }
        System.out.println("1");
        int mid = (left+right)/2;//取中间值的下表
        int midVal = arr[mid];//取中间值
                
        if(findVal<midVal) {
            return binaryFind(arr,left,mid-1,findVal);//没找到继续左递归查找
        }else if(findVal>midVal) {
            return binaryFind(arr,mid+1,right,findVal);//没找到继续右递归查找
        }else {
            //此处创建集合是因为有可能数组中存在相同的数多次，所以都找出来，把他们的下标存在集合中
           List<Integer> list = new ArrayList<Integer>();
           //当查找的数在数组中存在时,mid就是已经找到的第一个下标，接着左边查找相同的值
           int temp = mid -1;
           while(true) {
               if(temp<0 || arr[temp]!=findVal) {
                   break;
               }
               list.add(temp);//如果找到相同的值就把下标存入list中
               temp-=1;//让下标减一，一直搜索到temp<0的位置
           }
           list.add(mid);//mid是已经找到的第一个下标,所以存入list
           temp = mid+1;//同理 往右查找
           while(true) {
               if(temp>arr.length-1 || arr[temp]!=findVal) {
                   break;
               }
               list.add(temp);
               temp+=1;
           }
           return list;
        }
    }
}