Nov 15

非递归二分查找一个元素在有序数组中应处的位置 不指定

felix021 @ 2011-11-15 18:02 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(4011) | Via 本站原创 | |
@2019-03-19 STL里的lowerbound算法简单有效。

该元素在数组中不一定存在,只是要找一个i,使得 arr[i] <= t <= arr[i+1]。非递归的代码看起来真蛋疼。
//区间是 [s, e),左闭右开,类似STL。
int binsearch(int arr[], int t, int s, int e)
{
    int left = s, right = e, mid;
    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] == t)
            return mid;
        else if (arr[mid] < t)
        {
                //right most    OR ...right here
            if (mid + 1 >= right || t < arr[mid + 1])
                return mid;
            else
                left = mid + 1;
        }
        else /* arr[mid] > t */
        {      //left most    OR ...right here
            if (mid - 1 < left || arr[mid - 1] <= t)
                return mid - 1;
            else
                //11.18.DELETED: right = mid - 1;
                right = mid; //[11.18.update]发现这里是个BUG……
        }
    }
    return -2; //bad range
}




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]