有序表的折半查找算法

有序表的折半查找算法，也称为二分查找算法。它是一种高效的查找算法，适用于已经按照升序（或降序）排列好的有序表。

折半查找的基本思想是：首先确定待查找区间的中间位置mid，然后将要查找的值与中间位置的值进行比较。如果待查找值等于中间位置的值，则查找成功；如果待查找值小于中间位置的值，则在左半部分继续查找；如果待查找值大于中间位置的值，则在右半部分继续查找。重复以上步骤，直到找到待查找值或者确定该值不存在。

以下是折半查找算法的伪代码：

binarySearch(array, target):
    left = 0
    right = length(array) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if array[mid] == target:
            return mid
        
        if array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

其中，array是有序表（数组）, target是待查找的值。算法使用两个指针left和right来表示待查找区间的左右边界。

该算法的时间复杂度为O(logn)，其中n是有序表的长度。因为每次比较都将待查找区间缩小一半，所以算法的查找效率非常高。但是，折半查找算法要求有序表是静态的，即不会频繁插入、删除元素，否则需要进行排序操作。