javascript折半查找详解

折半查找法：

在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：

1）     待查找数据值与中间元素值正好相等，则放回中间元素值的索引。

2）     待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），直到找到相等的值。

3）     待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），直到找到相等的值

4）     如果最后找不到相等的值，则返回错误提示信息。

按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为

log2(n+1)-1

代码如下:
//Data为要查找的数组，x为待查找数据值，beg为查找范围起始，last为查找范围终止 
//非递归法 
int BiSearch(int data[], const int x, int beg, int last) 
{ 
    int mid;//中间位置 
    if (beg > last) 
    { 
        return -1; 
    } 
    while(beg <= last) 
    { 
        mid = (beg + last) / 2; 
        if (x == data[mid] ) 
        { 
            return mid; 
        } 
        else if (data[mid] < x) 
        { 
            beg = mid + 1; 
        } 
        else if (data[mid] > x) 
        { 
            last = mid - 1; 
        } 
    } 
    return -1; 
} 
//递归法 
int IterBiSearch(int data[], const int x, int beg, int last) 
{ 
    int mid = -1; 
    mid = (beg + last) / 2; 
    if (x == data[mid]) 
    { 
        return mid; 
    } 
    else if (x < data[mid]) 
    {