第二十三章 Caché 算法与数据结构 二分查找

使用场景

• 二分查找法适用于 升序排列的数组，如果你所要操作的数组不是升序排序的，那么请用排序算法，排序一下。
• 使用二分查找法相比顺序查找 节约了时间的开销，但是增加了空间使用。因为需要动态记录起始索引和结束索引和中间索引。

时间复杂度

• 顺序查找 平均和最坏情况时间复杂度 ：O(n)
• 二分查找法 时间复杂度为：O(log2n)

算法描述

二分查找操作的数据集是一个有序的数据集。开始时，先找出有序集合中间的那个元素。如果此元素比要查找的元素大，就接着在较小的一个半区进行查找；反之，如果此元素比要找的元素小，就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程，直到找到要查找的元素或者数据集不能再分割。

image.png

完整实力

非递归

Class PHA.YX.Arithmetic.BinarySearch Extends %RegisteredObject
{

Method search(array As PHA.YX.Arithmetic.Array, x As %Integer)
{
    #dim low as %Integer = 0
    #dim high as %Integer = array.length() - 1
    while (low <= high){
        w "low:" _ low _ " high:" _high,!
        /* 取中间索引 */
        #dim middle as %Integer = (low + high) \ 2

        if (x = array.get(middle)){
            return middle
        } elseif (x < array.get(middle)){
            
            /* 如果所找的的数小于中间索引对应的值证明所要找的数在左半边,将中间索引前一位设置为终点索引 */
            s high = middle - 1
        }else{
            
            /* 如果所找的的数大于中间索引对应的值证明所要找的数在右半边,将中间索引后一位设置为开始索引 */
            s low = middle + 1
        }
    }
    return -1
}
}

递归

Method recursive(array As PHA.YX.Arithmetic.Array, data As %Integer, beginIndex As %Integer, endIndex As %Integer)
{
    #dim midIndex = (beginIndex + endIndex) \ 2
    if ((data < array.get(beginIndex)) || (data > array.get(endIndex)) || (beginIndex > endIndex)){
        return -1
    }
    
    if (data < array.get(midIndex)) {
        return ..recursive(array, data, beginIndex, midIndex - 1)
    } elseif (data > array.get(midIndex)){
        return ..recursive(array, data, midIndex + 1, endIndex)
    }else {
        return midIndex
    }
}

调用

/// w ##class(PHA.YX.Arithmetic).BinarySearch(77)
ClassMethod BinarySearch(x)
{
    #dim array as PHA.YX.Arithmetic.Array = ##class(PHA.YX.Arithmetic.Array).%New()
    d array.init(10)
    d array.insert(0,11)
    d array.insert(1,22)
    d array.insert(2,33)
    d array.insert(3,44)
    d array.insert(4,55)
    d array.insert(5,66)
    d array.insert(6,77)
    d array.insert(7,88)
    d array.insert(8,99)
    d array.insert(9,111)
    #dim search as PHA.YX.Arithmetic.BinarySearch = ##class(PHA.YX.Arithmetic.BinarySearch).%New() 
    s index = search.search(array, x)
    w "------非递归-----",!
    w index,!
    
    
    s index = search.recursive(array, x, 0, array.length() - 1)
    w "------递归-----",!
    w index,!
    q ""
}

DHC-APP>w ##class(PHA.YX.Arithmetic).BinarySearch(77)
low:0 high:9
low:5 high:9
low:5 high:6
low:6 high:6
------非递归-----
6
------递归-----
6