Algorithm - Binary Search（Java）

你的名字 2022-05-24 06:20 114阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

package chimomo.learning.java.algorithm.search;
    
    /**
     * @author Chimomo
     *
     * <p>
     * Prerequisite:
     *
     * The prerequisite of binary search:
     * 1. The searched sequence must be sequentially stored.
     * 2. The searched sequence must be sorted by keyword.
     * </p>
     */
    public class BinarySearch {
    
        /**
         * Recursively binary search x in sorted array a
         * with low as subscript lower bound and high as subscript upper bound.
         * Its 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.
         */
        private 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.
         * Its 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.
         */
        private 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;
        }
    
        /**
         * Test program
         *
         * @param args The arguments
         */
        public static void main(String[] args) {
            int[] arr = {-3, -1, 0, 6, 11, 16, 16, 22, 99, 99};
            System.out.println(String.format("Search %d recursively in array with result subscript: %d",
                    16, searchRecursively(arr, 16, 0, arr.length - 1)));
            System.out.println(String.format("Search %d circularly in array with result subscript: %d",
                    16, searchCircularly(arr, 16)));
        }
    
    }
    
    /* ------ Running Results ------
    Search 16 recursively in array with result subscript: 5
    Search 16 circularly in array with result subscript: 5
    
    */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter