複数の要素を探索する二分探索。例えば[1,2,2,3]から2を探すならば、2つ目と3つ目なので(1..2)を得たい。足止め食らったのでGistとして残す。

multibsearch.rb

def test
    
    arr = Array.new(rand(9..12)){rand(1..5)}.sort
    
    target = rand(1..5)
    
    puts "query : arr=[#{arr*","}] , find #{target}"
    
    # 下方優先二分探索
    l = 0
    h = arr.size - 1
    while l < h
        m = (l + h) / 2
        if arr[m] < target
            l = m + 1
        else
            h = m
        end
    end
    low = l
    
    # 上方優先二分探索
    l = 0
    h = arr.size - 1
    while l < h
        m = (l + h + 1) / 2
        if arr[m] > target
            h = m - 1
        else
            l = m
        end
    end
    high = l
    
    if arr[low] == target && arr[high] == target 
        puts "result : (#{low}..#{high})";
    else
        puts "result : not found"
    end
end

10.times{
    test
}