题目求助｜二分查找不同实现方法细节困惑

6735

发布于未知归属地

有老哥可以帮忙看一下这两种二分的不同实现吗（本次双周赛第三题）。啥时候取等号，啥时候不取等号，啥时候要加1，啥时候不用，菜鸡已经被杀哭了o(╥﹏╥)o
第一种：

        //二分查找
/*        for (int i = 0; i < n; i++) {   //要找到小于等于当前query的最大价格
            int left = 0, right = m - 1;
            while (left < right) {  //当left=right的时候相当于已经找到了小于等于当前query的最大值，不需要再进去，这和要找到某个相等的值有所不同
                //int mid = left + (right - left) / 2;
                int mid = left + (right - left) / 2 + 1;  //这个一定要加1，没太理解
                if (items[mid][0] > queries[i]) {   //当此时mid比当前query大时，肯定不满足条件，可以跳过
                    right = mid - 1;
                } else {    //小于等于时，可能满足条件，需要保留
                    left = mid;
                }
            }
            ans[i] = items[left][0] <= queries[i] ? items[left][1] : 0;
        }*/

第二种：

//这一种也能过，二分杀我，太多的细节了
for (int i = 0; i < n; i++) {   //要找到小于等于当前query的最大价格
    int left = 0, right = m - 1;
    while (left <= right) {  
        int mid = left + (right - left) / 2;
        //int mid = left + (right - left) / 2 + 1;  //这个一定要加1，没太理解
        if (items[mid][0] > queries[i]) {  
            right = mid - 1;
        } else {   
            left = mid + 1;
            ans[i] = items[mid][1];
        }
    }
    //ans[i] = items[left][0] <= queries[i] ? items[left][1] : 0;
}