Searching Algorithms - tenji/ks GitHub Wiki

查找算法汇总

查找算法包括：

  • 顺序查找
  • 二分查找
  • 分块查找
  • 散列查找
  • 二叉排序树查找
  • B 树（主要用于查找磁盘数据）

一、顺序查找

思想：从头到尾一个一个比较

时间复杂度：O(n)

Java 实现：

public static int seqSearch(List<Integer> arr, int key) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr.get(i) == Integer.valueOf(key)) {
            return i;
        }
    }

    return -1;
}

二、二分查找

思想：分而治之，若要查找的 key 比当前的值小则在左半部分查找，否则在右半部分找，每次缩小一半查找范围。直到找到或者没找到，没找到的条件是起始位置大于终止位置。

限制：待查找的数组有序，且不能用于链表的查找

时间复杂度：O(logn)

Java 实现：

// 非递归实现
public static int binSearch(List<Integer> arr, int key, int low, int high) {
    int middle = (low + high) / 2;
    while (low <= high) {
        if (arr.get(middle) < key) {
            low = middle + 1;
        } else if (arr.get(middle) > key) {
            high = middle - 1;
        } else {
            return middle;
        }
        middle = (low + high) / 2;
    }
    return -1;
}
// 递归实现
public static int binSearchRecur(List<Integer> arr, int key, int low, int high) {
    if (low > high)
        return -1;
    int middle = (low + high) / 2;
    if (arr.get(middle) == key) {
        return middle;
    }
    if (arr.get(middle) < key) {
        return binSearchRecur(arr, key, middle + 1, high);
    } else {
        return binSearchRecur(arr, key, low, middle - 1);
    }
}

三、分块查找

四、散列查找

五、二叉排序树查找

二叉查找树又叫二叉排序树，是满足 左子节点 < 根节点 < 右子节点 的二叉树。

思想：从根节点开始比较，比节点小则查找左子树，比节点大则查找右子树，相等返回。递归进行。

Java 实现：

// 节点结构
static class node {
    int value;
    node leftChild;
    node rightChild;
}
// 递归实现
public static node BSTSearch(node head, int key) {
    if (key == head.value) {
        return head;
    } else if (key < head.value) {
        return BSTSearch(head.leftChild, key);
    } else {
        return BSTSearch(head.rightChild, key);
    }
}
// 非递归实现
public static node BSTSearch(node head, int key) {
    while (head.value != key) {
        if (key < head.value) {
            head = head.leftChild;
        } else {
            head = head.rightChild;
        }
        if (head == null) {
            break;
        }
    }
    return head;
}
⚠️ **GitHub.com Fallback** ⚠️