代码之家 › 专栏 › 技术社区 › uvett

这种“二进制”计数方法的通用名称是什么?应该怎么做?

binary-search bash

0

uvett · 技术社区 · 12 年前

下面的脚本是我对一个脚本的研究,我使用该脚本来抓取网页,其中包含指向未知数量的顺序编号文件的链接。为了创建尽可能少的无用请求,抓取脚本以“二进制”方式猜测文件的数量。

这个“研究”脚本可以选择猜测1美元作为出发点,以查找目录中.txt文件的数量。当我写这篇文章时,我有一种重新发明轮子的感觉。

这种计数方式叫什么?在《巴什》中怎么能不那么笨拙呢?

#!/bin/bash

set_SEARCH()
{
    DIVIDED=$SEARCH
    SEARCH=$(($SEARCH * 2))
}

increase_SEARCH()
{
    SEARCH=$(($SEARCH + $DIVIDED))
    DIVIDED=$(($DIVIDED / 2))
    #echo $DIVIDED
}

decrease_SEARCH()
{
    SEARCH=$(($SEARCH - $DIVIDED))
    DIVIDED=$(($DIVIDED / 2))
    #echo $DIVIDED
}

test_SEARCH()
{
    while [ -f "$(($SEARCH * 2)).txt" ]
    do
        set_SEARCH
    done
    if [ -f "${SEARCH}.txt" ]
    then
        echo "Trying $SEARCH"
        if [ "$DIVIDED" = 0 ]
        then
            NUMBER=$(($SEARCH + 0))
            echo "The number is $NUMBER"
            exit
        fi
        increase_SEARCH
        test_SEARCH
    else
        echo "Trying $SEARCH"
        if [ "$DIVIDED" = 0 ]
        then
            NUMBER=$(($SEARCH - 1))
            echo "The number is $NUMBER"
            exit
        fi
        decrease_SEARCH
        test_SEARCH
    fi 
}

SEARCH=2
while   [[ "$SEARCH" -le "$1" ]] ;
do
    SEARCH=$(($SEARCH * 2))
done
DIVIDED=$(($SEARCH / 2))

test_SEARCH

1 回复 | 直到 12 年前

1

that other guy 12 年前

这是具有未知上界的二进制搜索。了解了这一点,我们可以轻松编写/调整实现:

upper=42  # an arbitrary number >= 1
lower=0
while [[ -f $upper.txt ]]
do
    lower=$upper
    (( upper*= 2 ))
done

while (( lower < upper-1 ))
do
    middle=$(((lower+upper)/2))
    if [[ -f $middle.txt ]]
    then
        lower=$middle
    else
        upper=$middle
    fi
done

echo "The number is $lower"