二分法查找，哎，终究挤不进那10%

看到JavaEye上一个“很老”的新闻（囧） - 你是那10%可以实现二分查找算法的程序员吗？

 

哎，大学学的那些东西，已经忘记得差不多了，当作回顾吧，按照作者的约定，写一个试试。

 

 

<script type="text/javascript">
function binarySearch(arr, a) {
    var low = 0, high = arr.length - 1, index = -1;
    
    if (a < arr[low] || a > arr[high]) 
        return index;
        
    while (low <= high) {
        var i = parseInt((low+high)/2)
        var b = arr[i];
        if (a == b) {
            index = i;
            break;
        } else if (a < b) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    
    return index;
}

function println(str) {
    document.write((str||'') + "<br/>");
}

function testSearch(arr, values) {
    for (var i = 0; i < values.length; i++) {
        println("found " + values[i] + " at " + binarySearch(arr, values[i]));
    }
}

var arr = [1, 3, 4, 12, 88, 168, 169, 172];
var arr1 = [1, 3, 4, 12, 88, 168, 169];
var test = [0, 5, 89, 167.5, 199];

println("[" + arr + "]");
testSearch(arr, arr);
testSearch(arr, test);
println();
println("[" + arr1 + "]");
testSearch(arr1, arr1);
testSearch(arr1, test);
</script>

 

虽然很快写完，但还是漏了东西， 写成了  high = i - 1; 和  low = i + 1; 于是乎死循环，悲哀，看来知识这东西，还得经常回顾。

 

评论

1 楼 lyyu1988 2011-05-21  

二分查找要求查找的数组按顺序排列！我都老长时间没写过了，闲了写一个，呵呵！