查找算法复习

查找算法的一些笔记。

顺序查找

最简单粗暴的查找方式,直接对数组进行遍历即可。

/**
 * @author 陶波利
 */
public class OrderSearch {
    public static boolean orderSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 5, 6, 7, 8, 12, 213, 45, 5123, 4123, 5};
        int key = 5;
        System.out.println(orderSearch(arr, key));
    }
}

二分查找

二分查找要求数组有序,以下是在数组中使用二分查找算法查找 23 的例子(图源 GeeksforGeeks):

图源:GeeksforGeeks

代码:

/**
 * @author 陶波利
 */
public class BinarySearch {
    static int binarySearch(int[] arr, int x) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == x) {
                return m;
            }
            if (arr[m] < x) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 5, 6, 7, 8, 12, 45, 213, 4123, 5123};
        int x = 5123;
        System.out.println(binarySearch(arr, x));
    }
}

二分搜索树

关于二分搜索树查找算法在本人博客文章 BST 中的 contains() 方法中已经实现。GitHub:DataStructReview/BST.java at master · bolitao/DataStructReview

private boolean contains(Node root, E e) {
    if (root == null) {
        return false;
    }
    if (e.compareTo(root.e) == 0) {
        return true;
    } else if (e.compareTo(root.e) < 0) {
        return contains(root.left, e);
    } else {
        return contains(root.right, e);
    }
}

参考

Binary Search - GeeksforGeeks

updatedupdated2020-10-102020-10-10
加载评论