10.查找算法

在java中，我们常用四种查找算法：

  1.顺序查找(线性)

  2.二分法/折半查找

  3.插值查找

  4.斐波那契查找

1.线性查找.

2.二分查找算法

二分查找：

对一个 进行二分查找{1,8,10,89,1000,1234},输入一个数，看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"  

样例：
public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 1000, 1234};
        int index = binarySearch(arr, 0, arr.length-1, 5);
        System.out.println("找到了，下标为：" + index);
    }

    /**
     * 二分查找算法
     *
     * @param arr         数组
     * @param left        左索引
     * @param right       右索引
     * @param searchValue 查找数字
     * @return 找到的元素下标, 没找到返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int searchValue) {
        //当左索引大于右索引时
        if (left > right) {
            return -1;
        }
        //找到中间位置下标
        int middle = (left + right) / 2;
        if (searchValue < arr[middle]) {
            //这里需要注意，middle-1，不这么操作会造成死递归
            return binarySearch(arr, left, middle-1, searchValue);
        } else if (searchValue > arr[middle]) {
            //这里需要注意，middle+1
            return binarySearch(arr, middle+1, right, searchValue);
        } else {
            return middle;
        }
    }
}

思考：在{1,8,10,89,1000,1000,1000,1000,1234}中输出1000的所有下标

 public static List binarySearch2(int[] arr, int left, int right, int searchValue) {
        //当左索引大于右索引时，没找到
        if (left > right) {
            return null;
        }
        //找到中间位置下标
        int middle = (left + right) / 2;
        if (searchValue < arr[middle]) {
            //这里需要注意，middle-1，不这么操作会造成死递归
            return binarySearch2(arr, left, middle - 1, searchValue);
        } else if (searchValue > arr[middle]) {
            //这里需要注意，middle+1
            return binarySearch2(arr, middle + 1, right, searchValue);
        } else {
            /*
                重点1：
                这里在返回之前向左，和向右扫描，拿到所有相同的数的下标
             */
            List<Integer> list = new ArrayList<>();
            list.add(middle);
            int i = middle;
            //向左找
            while (arr[i - 1] == searchValue) {
                list.add(i - 1);
                i -= 1;
            }
            //向右找
            i = middle;
            while (arr[i + 1] == searchValue) {
                list.add(i + 1);
                i += 1;
            }
            return list;
        }
    }