欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法 - 折半查找(Java)

程序员文章站 2024-03-01 09:14:16
...
/*
 *  Chimomo's Blog: https://blog.csdn.net/chimomo/
 */
package chimomo.learning.java.algorithm.search;

/**
 *
 * @author Chimomo
 *
 * The prerequisite of binary search:
 * <li>
 * 1. The searched sequence must be sequential stored.
 * </li>
 * <li>
 * 2. The searched sequence must be sorted by keyword.
 * </li>
 */
public class BinarySearch {

    /**
     * Recursively binary search x in sorted array a with low subscript lower
     * bound and high subscript upper bound.
     *
     * Time complexity is O(log2n).
     *
     * @param a The array to be searched
     * @param x The searched target
     * @param low The subscript lower bound of array a
     * @param high The subscript upper bound of array a
     * @return The subscript of x in the array a if found, -1 otherwise.
     */
    public static int searchRecursively(int[] a, int x, int low, int high) {
        // Not found.
        if (low > high) {
            return -1;
        }

        int mid = (low + high) >> 1;

        if (x == a[mid]) {
            return mid;
        }

        return x < a[mid] ? searchRecursively(a, x, low, mid - 1) : searchRecursively(a, x, mid + 1, high);
    }

    /**
     * Circularly binary search x in sorted array a.
     *
     * Time complexity is O(log2n).
     *
     * @param a The array to be searched
     * @param x The searched target
     * @return The subscript of x in the array a if found, -1 otherwise.
     */
    public static int searchCircularly(int[] a, int x) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (a[mid] == x) {
                return mid;
            }

            if (a[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }

}