首页 > 试题广场 >

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

[问答题]

以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标元素相等时，返回最后一个元素的下标，目标元素不存在时返回-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;

}


添加回答
乌龙阁头像 乌龙阁
if (data[mid] <= target) 
     left = mid + 1;
这两行搭配有问题，

if (data[right] == target)

       return right;

这里写在while循环的外面，有问题，while跳出循环的条件是 left>=right;  此处判断应该放在while之前，并且在while内新增 = target的判断
 
发表于 2019-09-08 00:47:28 回复(0)
更多回答
夜仙森Yuki头像 夜仙森Yuki
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
1
intright = 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'.
1
2
3
4
if(data[mid] <= target)
    left = mid;
else 
    right = mid;
To avoid the infinite loop, we make the while loop as
1
while(left + 1< right)
4. At last, when we judge the index, we only need to see the value at left and right. So,
1
2
3
4
5
if(data[right] == target) 
    returnright;
if(data[left] == target)
    returnleft;
return-1;
5. Some minor issue include the mid calculation. To avoid overflow, we'd better change mid calculation to
1
intmid = left + (right - left) / 2;

Overall, the program(in Java) should be:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
intBinarySeachMax(int[] data, inttarget) {
    intlen = data.length;
    intleft = 0;
    intright = len - 1;
    while(left + 1< right) {
        intmid = left + (right - left) / 2;
        if(data[mid] <= target) {
            left = mid;
        }
        else{
            right = mid;
        }
    }
    if(array[right] == target) {
        returnright;
    }
    if(array[left] == target) {
        returnleft;
    }
    return-1;
}

发表于 2021-03-05 02:50:11 回复(1)
jojomango99头像 jojomango99

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

{

   int left = 0;

   int right = data.size() - 1; // 最後一個index

   while (left < right) {

       int mid = (left + right) / 2;
       if (data[mid] == target) // mid的判斷應在這, 符合的話就可以結束運算

       return mid;

       if (data[mid] < target) // '=' 的話就已經從上方判斷結束，拿掉'='

           left = mid + 1;

       else

           right = mid - 1;

   }   

   return -1;

}

发表于 2018-04-23 15:11:48 回复(2)
无名111头像 无名111
1. (left + right) / 2可能会溢出，正确是(left + (right - left) / 2);
发表于 2019-03-02 14:11:24 回复(2)
牛排君头像 牛排君
1、当data大小为零时，明显会出错，应该先判断一下。
2、 right 应该等于 data.size()-1，否则当目标出现在data最右边或比data中所有的数大时，会访问越界。
修改后的代码如下 

int BinarySearchMax(const vector<int>& data, int target)
 {
 if (data.size() == 0)
 return -1;
 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 (data[right] == target)
 return right;
 return -1;
 }

编辑于 2018-10-24 00:10:31 回复(4)
chenkun0402头像 chenkun0402 
while (left < right){
  int mid = (left + right) / 2;
  if (data[mid] < target){
    left = mid + 1;
  }else if (data[mid] > target){
    right = mid - 1;
  }else{
    //euqals,move left, right keep still.
    left = mid;
  }

}

发表于 2018-08-09 22:23:02 回复(0)
牛客495266626号头像 牛客495266626号
right=data.size()-1;
left==right;
data[mid] <= target ==逻辑有问题

发表于 2022-03-05 16:06:47 回复(0)
虹niji头像 虹niji
1.保证left指向所查询数字在数组中最后一次出现地方的下标+1
2.当right在left左边1位的时候，即right指向所查询数字 
int BinarySearchMax(const std::vector<int>& data, int target)
{
   if (data.size () ==0)
       return -1;           //防止right[-1]indexError

   int left = 0;

   int right = data.size() - 1; // 返回最后一个index

   while (left <= right) {  //当right在left左边时跳出循环

       int mid = left + (right - left) / 2; //防止left+right整数溢出

       if (data[mid] <= target)

           left = mid + 1;

       else

           right = mid - 1;

   }

   if (data[right] == target)

       return right;

   return -1;

}


发表于 2021-08-28 00:42:46 回复(0)
Slate_js头像 Slate_js
int BinarySearchMax(const vector<int>& data, int target)
{
    if (data.size() == 0)         
        return -1;
    int left = 0;
    int right = data.size() - 1;    
    while (left <= right) {             //当l>r时，循环即终止。最后的情况只有两种可能：1. right 指向最后的目标元素 2. 不存在目标元素
        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;
}
发表于 2021-03-30 15:01:18 回复(0)
公孙杰头像 公孙杰
链接：https://www.nowcoder.com/questionTerminal/5529d0527b5d4c11a69f1ce47a09ba32
来源：牛客网

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

{

   int left = 0;
    ///////////// data为空时返回-1
    if (data.size() == 0) { 
        return -1;
    }
    ///////////
   // int right = data.size();  // 下标保证不越界
    int right = data.size() - 1; 

       int mid = (left + right) / 2;

       if (data[mid] <= target)

           // left = mid + 1; // 选取重复元素的最后一个
            left = mid;

           right = mid - 1;

   }

   if (data[right] == target)

       return right;

   return -1;

}

发表于 2021-03-26 12:18:56 回复(0)
牛客904207443号头像 牛客904207443号 
int mid = (left + right) / 2;
需先判断奇数个元素或偶数个元素，然后进行中间位置的判断； 
if (data[right] == target)
       return right;
不能体现是最后一个相同元素的下标，需递增下标查询直到于目标元素不一样；

发表于 2020-10-10 20:39:30 回复(0)
牛客820614800号头像 牛客820614800号
left 可以等于 right
再while循环中当data[mid] == target的时候，这个函数会错过这个target因为<=target后会将left限制至>= mid +1从而错过target
发表于 2020-09-19 12:32:49 回复(0)
给一口饭吃吧头像 给一口饭吃吧 
int BinarySearchMax(const std::vector<int>& data, int target)
{
   int left = 0;
   int right = data.size()-1;//应该加个减1，为最右下标
   while (left < right) {
       int mid = (left + right) / 2;
       if (data[mid]==target){//当有多个元素值与目标元素相等时，返回最后一个元素的下标
          int now=mid;
          while(data[now]==data[now+1]) now++;
          return now;
       }
       else if (data[mid] <target)
           left = mid + 1;
       else
           right = mid - 1;
   }
   if (data[right] == target)
       return right;
   return -1;
}

发表于 2020-09-11 11:37:26 回复(0)
风声lyw头像 风声lyw
int binary1(const std::vector<int>&data,int target){
 int left = 0;
 //int right = data.size()-1;
  int right = data.size();
 cout<<right<<endl;
 while(left<right) {
  int mid = (left + right)/2;
  if(data[mid] <= target)
  left = mid+1;
  else
  right = mid ;
 }
 if(data[left-1] == target)
  return left-1;
 return -1;
}
发表于 2020-08-25 14:51:50 回复(0)
何晗头像 何晗
function binarySearch(data, target) {
    let left = 0,
        right = data.length;
    while (left < right) {
        let mid = ((left + right) / 2) | 0;
        if (data[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (data[right - 1] == target) {
        return right - 1;
    }
    return -1;
}
就一个错误，最后部分，right改成right-1。

发表于 2020-08-22 02:50:33 回复(0)
大肥凯头像 大肥凯

正确写法（一般可以选择“左闭右开”）：

function binarySearch (data, target) {
  let [left, right] = [0, data.length]

  while (left < right) {
    const mid = left + (right - left >>> 1)
    if (target < data[mid]) {
      right = mid
    } else {
      left = mid + 1
    }
  }

  // 此时left、right相等，随便用一个
  let res = -1
  if (data[right - 1] === target) {
    res = right - 1
  }
  return res
}

综上，题目所含错误有：

  1. 当target ，应该是right = mid`，右边界为开区间
  2. 最终判断相等时，条件应该是data[right-1] === target，并且返回值也应该是right-1
编辑于 2019-10-30 08:48:28 回复(0)
Chen.NB头像 Chen.NB 


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 (data[right] == target)

       return right;

   return -1;

}

   

发表于 2019-08-25 11:02:29 回复(1)
小狒头像 小狒
    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[left] == target)
           returnleft;     return-1;
}
发表于 2019-07-12 18:09:50 回复(0)
gislfzhao头像 gislfzhao
链接：https://www.nowcoder.com/questionTerminal/5529d0527b5d4c11a69f1ce47a09ba32
来源：牛客网

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 + 1;

       else

           right = mid - 1;

   }

   if (data[right] == target)

       return right;

   return -1;

}

发表于 2019-07-05 17:46:19 回复(0)
Lhy_xxy头像 Lhy_xxy 
function BinarySearchMax(arr, target) { let s = 0;  let e = arr.length - 1;  let m = Math.floor((s + e) / 2);   while (s < e && arr[m] !== target) { if (arr[m] > target) {
            e = m - 1  } else {
            s = m + 1  }
 m = Math.floor((s + e) / 2);  } if (arr[m] == target) { return m;  } else {  return -1;  }
}

发表于 2019-07-04 19:37:33 回复(1)
提交观点

问题信息

前端工程师 2018 字节跳动
上传者：小小
难度：
33条回答 3132浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号