魔改的二分法

魔改二分法，多个重复值下标二分法查找

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

public class BinarySearch{
    /**
     *
     * @param array  参数数组
     * @param target 查找的目标值
     * @return  目标值所在的下标的集合
     */
    public static List<Object> binarySearch(Object array[], Object target){
        //最左下标
        int left = 0;
        //最右下标
        int right = array.length -1;
        //用于存储重复元素的下标集合
        List result = new ArrayList();
        while (left <= right){
            //二分查找中间值
            int mid = (left + right) / 2;
            //如果中间值等于目标值
            if(array[mid].equals(target)){
                if(mid > 0){
                    //看前一个元素是否也等于目标值
                    if(array[mid -1].equals(target)){
                        for(int i = mid - 1; i>=0; i--){
                            if(array[i] == target){
                                //添加排在所查到的值的前边的相同的下标
                                result.add(i);
                            }else break;
                        }
                    }
                }
                //添加第一次查到的目标值的下标
                result.add(mid);
                if(mid < right){
                    //看后一个元素是否也等于目标值
                    if(array[mid + 1].equals(target)){
                        for (int i = mid + 1; i<=right; i++){
                            if(array[i].equals(target)){
                                //目标值相等则将下标添加到集合中
                                //添加所查到的目标值后边的相同的下标
                                result.add(i);
                            }else break;
                        }
                    }
                }
                return result;
                //为了避免不同数据类型比较大小的差异，都将数据转换为String类型进行比较
            }else if((target.toString().compareTo(array[mid].toString())) < 0){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        if(result.size() == 0){
            //如果没有找到目标值，则返回-1
            result.add(-1);
        }
        return result;
    }

    public static void main(String[] args) {
        Double array[] = {55.2,65.5,47.5,47.5,82.6};
//        String array[] = {"123","123","121","121","456"};
        //将数组排序
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        System.out.println(binarySearch(array, 47.5));
    }
}

这就是在经典的二分法基础上，通过向左向右循环查找相同目标值下边，返回所有重复下标的解法。
平时提起二分法都有印象，但是突然让你改一下，一时半会还不知道动哪里合适。
ps：记住了，面试贼容易问，跟语言无关，记住思路最重要。