首页 > 试题广场 >

以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标

[问答题]

以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标元素相等时，返回最后一个元素的下标，目标元素不存在时返回-1。请指出程序代码中错误或不符最佳实践的地方（问题不止一处，请尽量找出所有你认为有问题的地方）

int BinarySearchMax(const std::vector<int>& data, int target)

{

int left = 0;

int right = data.size();

while (left < right) {

int mid = (left + right) / 2;

if (data[mid] <= target)

left = mid + 1;

else

right = mid - 1;

}

if (data[right] == target)

return right;

return -1;

}

一叶之秋~

1. int right = data.size(); //这行话如果所有的值都比目标值小的话，会导致数组越界，改为 int right = data.size() - 1;

2. while (left < right) { //这句话应该改为left<=right，根据上面的修改，避免最后无法探测到right下标的值，改为while (left <= right) {更好

3. int mid = (left + right) / 2; //这句话这样子写可能会导致死循环，改为int mid = left + (right - left) / 2即可避免

最终的代码为：

int BinarySearchMax(const std::vector<int>& data, int target)
{
   int left = 0;
   int right = data.size()-1;
   while (left <= right) {
       int mid = left + (right - left) / 2;
       if (data[mid] <= target)
           left = mid + 1;
       else
           right = mid - 1;
   }
   if (data[right] == target)
       return right;
   return -1;
}

发表于 2018-09-05 18:40:21 回复(0)

更多回答

代码一条龙

int BinarySearchMax(const std::vector<int>& data, int target)
{
int left = 0;
int right = data.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (data[mid] <= target)
left = mid + 1;
else
right = mid - 1;
}
if (right >= 0 && data[right] == target)
return right;
return -1;
}

发表于 2021-07-11 20:19:24 回复(0)

难~

if (data[mid] <= target)

left = mid + 1;

当要查找的目标元素恰好为data[mid]时，将会错过该元素

可以通过判断data[mid+1]的值是否为目标元素（如果没越界的话）来纠正算法，下面为改正后的例子：

int BinarySearchMax(int[] data, int target)
    {
        int left = 0;
        int right = data.length;
        while (left <= right && left<data.length) {
            int mid = (left + right) / 2;
            if ((mid+1<data.length-1 && data[mid+1] == target) || data[mid] < target)//data[mid] == target 判断右边是否还有连续的target值
                left = mid + 1;
            else if (data[mid] > target)
                right = mid - 1;
            else if(data[mid] == target)//data[mid] == target 且右边无target值
                    return mid;
        }
        return -1;
    }

发表于 2020-08-07 21:56:04 回复(0)

等我在未来

int BinarySearchMax(int[] a, int target){
    int left = 0;
    int right = a.length-1;
    int n = 0;//用于获取下标值
    while(left<right){//确保left=right时跳出循环
        int mid = (left+right)/2;
        if(a[mid]<=target){
            left = mid+1;
            if(a[mid]==target)
                n = mid;//暂存符合查找值的下标,可覆盖
        }else{
            right = mid;
        }
    }
    if(a[right]==target){//判断最后一次比较是否相同  结束循环后要么right=left=0,要么right=left=a.length-1;
        n = right;
    }
    if(n!=0){
        return n;
    }else{
        return -1;
    }
        
}

发表于 2020-07-13 13:18:30 回复(0)

StanWind

循环条件不对，要取右边得加等号，出循环的下标可能越界

发表于 2018-02-06 13:52:36 回复(2)

Cappuccinuo

1. If the number array is [0, 1, 1, 1], and we want to find the last index of 1, the program will raise ArrayIndexOutOfBoundException: 4. As the left position will become 4 at the end, and right will still be data.size() = 4, data[right] will be out of bound.

2. To fix that, we first need to change the right start point to

int right = data.size() - 1;

3. When data[mid] is smaller or equal to target, we should not make left as mid + 1, as data[mid] might be the last '1'.

if (data[mid] <= target)
    left = mid;
else 
    right = mid;

To avoid the infinite loop, we make the while loop as

while (left + 1 < right)

4. At last, when we judge the index, we only need to see the value at left and right. So,

if (data[right] == target) 
    return right;
if (data[left] == target)
    return left;
return -1;

5. Some minor issue include the mid calculation. To avoid overflow, we'd better change mid calculation to

int mid = left + (right - left) / 2;

Overall, the program(in Java) should be:

int BinarySeachMax(int[] data, int target) {
    int len = data.length;
    int left = 0;
    int right = len - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (data[mid] <= target) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    if (array[right] == target) {
        return right;
    }
    if (array[left] == target) {
        return left;
    }
    return -1;
}

编辑于 2019-04-14 00:04:16 回复(1)

ym130

int BinarySearchMax(const std::vector<int>& data, int target)

{

int left = 0;

int right = data.size(); //应该为int right =data.size()-1;

while (left < right) { //应该为while（left<=right ）

int mid = (left + right) / 2;

if (data[mid] <= target)

left = mid + 1;

else

right = mid - 1;

}

if (data[right] == target)

return right;

return -1;

}

发表于 2018-08-11 11:22:49 回复(3)

啦啦啦201804181716816

int BinarySearchMax(const std::vector<int>& data, int target)

{

int left = 0;

int right = data.size()-1;

while (left < right) {

int mid = (left + right) / 2;

if (data[mid] <= target)

left = mid;

else

right = mid - 1;

}

if (data[left] == target)

return left;

return -1;

}

发表于 2018-08-08 23:09:23 回复(3)

Alkiadling

public int binarySearchMax(int[] data, int target){
    int left = 0, right = data.length - 1;
    while (left < right){
        int mid = left + (right - left + 1) / 2;
        if(data[mid] > target){
            right = mid - 1;
        }else{
            left = mid;
        }
    }
    return data[left] == target ? left : -1;
}

发表于 2022-02-25 15:55:09 回复(0)

aler

int BinarySearchMax(const std::vector<int>& data, int target)
{
   int left = 0;
   int right = data.size() - 1;
   while (left <= right) {
       int mid = (left + right) / 2;
       if (data[mid] <= target)
           left = mid + 1;
       else
           right = mid - 1;
   }
   if (right >= 0 && right < data.size() && data[right] == target)
       return right;
   return -1;
}

发表于 2018-03-21 16:29:53 回复(2)

青春猪头少年不会没有offer

int BinarySearchMax(const std::vector<int>& data, int target)

{

   int left = 0;

   int right = data.size() - 1;    

   while (left < right) {

       int mid = (left + right + 1) / 2;

       if (data[mid] <= target)

           left = mid;

       else

           right = mid - 1;

   }

   if (data[right] == target)

       return right;

   return -1;

}

编辑于 2023-12-21 21:53:41 回复(0)

Lana_dr

取中间点处应该使用left+（right-left）/2 防止溢出

发表于 2023-09-01 15:44:55 回复(0)

牛客59976975号

1. right的初始值应该为 data.size() - 1;

2. mid = (left + right) / 2这样的运算方式可能导致 left + right 时的结果溢出导致报错。应该更换为 left + (right - left >> 1) . 用位运算代替 / 2会更高效

3. 当返回的下标为数组的0号索引时。该方法的会返回-1。所以循环条件应改成 while (left <= right);

发表于 2022-04-08 23:03:55 回复(0)

梧桐雨下雨梧桐

1.int right = data.size();

此处将其改为

int right = data.size()-1;

2.if (data[mid] <= target){

left = mid + 1;

}

此处将其改为

if (data[mid] <= target){

left = mid;

}

发表于 2022-02-16 20:21:36 回复(0)

The233mmDaJJ

right 应该初始化为data.size() - 1

否则当最后一个元素<=target 时 mid 会被赋值为data.size() ，data[mid]会发生越界访问

while(left<right) 改成 while(left<=right)

这样才能保证 while退出时right == left - 1 && data[left] > target && data[right]<=target(不考录越界)

if(data[right] == target) 有可能因为right == -1 而产生越界访问

应该改成

if(right!=-1&&date[right] == target)

return right;

return -1;

发表于 2021-09-11 21:19:50 回复(0)

一只小逸白

int BinarySearchMax(const std::vector<int>& data, int target)

{

int left = 0;

int right = data.size()-1;

while (left + 1< right) {

int mid = (left + right) / 2;

if (data[mid] <= target)

left = mid;

else

right = mid - 1;

}

if (data[right] == target)

return right;

if (data[left] == target)

return left;

return -1;

}

发表于 2021-07-16 23:32:20 回复(0)

ToddGao

1、在计算 mid 时这样可能会溢出，最佳实践是 int mid = left + (right - left) / 2 或使用位移

2、右边届的收缩应该是 right = mid

发表于 2021-06-08 15:03:36 回复(0)

冷朴承

1.在最开始需要对数组判空，避免空指针异常；

2.if(data[right==target）应该放到while循环内部，并放在首行

发表于 2020-08-09 14:26:22 回复(0)

jsddseven

int BinarySearchMax(const std::vector<int>& data, int target)

{

int left = 0;

int right = data.size();

while (left < right) {

int mid = (left + right) / 2;

if (data[mid] <= target)

left = mid + 1;

else

right = mid;

}

if (data[right-1] == target)

return right;

return -1;

}

发表于 2020-06-08 10:36:18 回复(0)

coyorkdow

mid = (left + right) / 2; 可能会有溢出，应该改为mid = left+((right-left)>>1);

right的值可能为data.size()或者-1，因此 if (data[right] == target)应该改为 if (right!=-1&&right!=(int)data.size()&&data[right] == target)。

最理想的实现为

int BinarySearchMax(const std::vector<int>& data, int target)
{
   int left = 0;
   int right = data.size();
   while (left < right) {
       int mid = left + ((right-left)>>1);
       if (data[mid] <= target)
           left = mid + 1;
       else
           right = mid;
   }
   right--;
   if(right >=0 && data[right] == target)
       return right;
   return -1;

}

发表于 2020-02-03 16:40:50 回复(0)

希陌

  
int BinarySearchMax(const std::vector<int>& data, int target){
   int left = 0;
   int right = data.size();
    while(left < right){
        int mid = (left+right)/2;
        if(a[mid] > target) //寻找第一个比目标值大的数下标
            right = mid;
        else
            left = mid + 1;
    }
    if(left == 0) //新增判断条件
        return -1;
    if(a[left-1] != target)       
               return -1;
    return left-1;
    }

}

发表于 2020-01-22 20:59:48 回复(0)

提交观点

问题信息

上传者：小小

难度：

56条回答 95收藏 4811浏览

以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标

问题信息

热门推荐

相关试题