数组查找

顺序查找

• 适用于无序和有序线性表
• 从线性表的一端开始，逐个检查每个元素，直到找到所需的元素或检查完所有元素为止。

FUNCTION SequentialSearch(A[0...n-1], value):
    FOR i = 0 TO n-1 DO
        IF A[i] == value THEN
            RETURN i    // index of the found value
        END IF
    END FOR
    RETURN -1   // value not found
END FUNCTION

时间复杂度为$O(n)$

折半查找

• 只能应用于有序列表
• 它涉及将列表分成两半，并确定所需元素可能在哪一半中，然后对所选的那一半重复此过程。

FUNCTION BinarySearch(A[0...n-1], value):
    low = 0
    high = n-1
    WHILE low <= high DO
        mid = (low + high) / 2
        IF A[mid] == value THEN
            RETURN mid  // index of the found value
        ELSE IF A[mid] < value THEN
            low = mid + 1
        ELSE
            high = mid - 1
        END IF
    END WHILE
    RETURN -1  // value not found
END FUNCTION

时间复杂度为$O(log_2{n})$

分块查找

线性表的分块查找通常应用于一种特定的情境：线性表（例如数组）被分为多个大小相等（或者最后一个块可能较小）的块，并且块内的元素是无序的，但是块与块之间是有序的。也就是说，每个块内的最大（或最小）元素小于下一个块的任意元素。

常用的分块查找策略如下：

1. 先对块索引进行顺序或二分查找以确定所需元素可能所在的块。
2. 然后在确定的块中进行顺序查找。