Java 使用二分查找快速定位元素位置

转载请注明出处：

　　快速定位 一个有序数列中 某一个元素的位置；

　　共有三种思路：

　　　　第一种：使用 for 循环，匹配元素值 与循环变量的值是否相等，相等则循环变量时的 i 则为元素位置

　　　　第二种：使用 二分法 与递归，二分法为折半思想，通过递归折半，找到元素的位置

　　　　第三种：使用 二分发 与 while 循环，在while 循环中，以 元素值得 最大值与最小值关系，在while 循环中，通过二分法，不断修改 元素区间的最大值与最小值

　　实现：

　　　　第一种 for 循环的代码省略。

　　　　第二种，使用 二分法 与 递归 与 第三种实现方式如下：

复制代码
package com.example.demo.lettcode;

/**
 * 使用二分查找，快速定位元素位置和是否存在
 * 当使用二分查找时，必须保证是有序数列，只有有序数列才能进行大小的左右分边
 */
public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1,3,4,5,6,7,8,12};
        System.out.println(arr.length);
        // 使用递归与二分法
        int index = binarySearch(arr,4,0,arr.length-1);
        System.out.println(index);
        // 使用while 循环与二分法
        int index2 = cycleFind(arr,4);
        System.out.println(index2);
    }

    /**
     * 使用递归与二分法
     * @param arr
     * @param value
     * @param start
     * @param end
     * @return
     */
    public static int binarySearch(int[] arr, int value, int start, int end) {
        //判断在有序列表中是否存在
        if (value < arr[start] || value > arr[end] || start > end) {
            return -1;
        }

        int middle = (start + end) / 2;
        int index = 0;
        if (arr[middle] > value) {
            //位于中间值得左边
            index = binarySearch(arr, value, start, middle - 1);
        } else if (arr[middle] < value) {
            // 位于中间值得右边
            index = binarySearch(arr, value,middle + 1, end );

        } else {
            return middle;
        }
        return index;
    }

    /**
     * 使用while循环与二分法
     * @param arr
     * @param value
     * @return
     */
    public static int cycleFind(int[] arr, int value) {
        int low = 0;
        int middle = 0;
        int high = arr.length - 1;

        while (low <= high) {
            middle = (low + high) / 2;
            if (arr[middle] > value) {
                high = middle - 1;
            } else if (arr[middle] < value) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

}
复制代码
 

　　分析：

　　　　使用递归方式时，递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的： 空间复杂度：O(log2N )

　　　　非递归方式时，空间复杂度为 O(1)

 

标签: 算法与数据结构