Module: CodeCook::Find

Defined in:
手写代码必备手册(Ruby版).rb

Overview

第六章 查找

Defined Under Namespace

Modules: HashSet

Class Method Summary (collapse)

Class Method Details

+ (Integer) binary_search(a = [], x)

6.1 二分查找/折半查找

有序顺序表的折半查找算法.

在Ruby中，Array::bsearch函数实现了二分查找.

Parameters:

  • a (Array) (defaults to: []) —

    存放数据元素的数组，查找前需要先排序

  • x (Integer) —

    被查找的元素

Returns:

  • (Integer) —

    如果找到x，则返回其数组下标 如果找不到 x 且 x 小于 array 中的一个或多个元素,则为一个负数,该负数是大 于 x 的第一个元素的索引。如果找不到 x 且 x 大于 array 中的任何元素,则为一个负数, 该负数是(最后一个元素的索引加 1)的所以呢。



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
# File '手写代码必备手册(Ruby版).rb', line 180

def binary_search(a=[], x)
    # 查找前先排序
    p a.sort!

    left = 0
    right = a.size - 1

    while left <= right
        mid = left + (right - left)/2
        if x > a[mid]
            left = mid + 1
        elsif x < a[mid]
            right = mid - 1;
        else
            return mid
        end
    end

    return -(left + 1)
end