我要招人

去企业版

首页 > 试题广场 >

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

[问答题]

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

2. if(data[mid] == target && data[mid+1] == target) left = mid+1;

else if(data[mid] == target && data[mid+1] != target) return mid;

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

else right = mid-1;

发表于 2019-02-15 17:50:22 回复(0)

CUMT-徐子康

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

发表于 2021-10-25 17:39:39 回复(0)

牛客290136415号

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-1] == target)
       return right-1;
   return -1;
}

发表于 2021-08-01 21:07:38 回复(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 (data[mid] <= target)

            left = mid + 1;

        else

            right = mid ;

    }

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

        return right-1;

    return -1;

}

发表于 2021-04-24 17:36:56 回复(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 (data[mid] <= target)

			left = mid + 1;

		else

			right = mid ;

	}

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

		return right-1;

	return -1;

}

发表于 2020-09-09 16:35:56 回复(0)

许愿offerer

1.int right = data.size() 改为 int right = data.size()-1;
2.int mid = (left + right)/2 改为 int mid = left + (right - left)>>1;
3.left = mid + 1 改为 left = mid;

发表于 2018-08-24 15:23:21 回复(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) / 2;  if (data[mid] <= target)
            left = mid + 1;  else  right = mid - 1;  } if (data[right] == target) return right;  return -1; }

发表于 2018-08-12 12:40:28 回复(0)

提交观点

问题信息

测试开发工程师 2018 字节跳动

上传者：小小

难度：

7条回答 45收藏 801浏览

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

问题信息

热门推荐

相关试题