等于二进制搜索的意义 [英] Significance of Equal To in Binary Search

问题描述

我在C ++中实现二进制搜索。这是我的代码：

  #include< iostream& 
 #include< vector> 
 #include< algorithm> 
 
 using namespace std; 
 
 int bs（vector< int> a，int val）
 {
 int l = 0，r = a.size 
 while（1 <= r）// == 
 {
 int mid = 1 +（r-1）/ 2的意义; 
 
 if（a [mid] == val）return mid; 
 if（a [mid]> val）
 {
 r = mid-1;继续; 
} 
 else 
 {
 l = mid + 1; 
} 
} 
 return l; //有意返回这个
} 
 
 int main（）
 {
 vector< int> a = {1,3}; 
 cout<< bs（a，1）<< endl; 
 return 0; 
} 
  

问题1 b

在某些实现中，我看到人们使用

  while（l< r）
  

  while（l <= r）
  

任何可能的错误来源，如果我不使用==？

问题2

如果没有找到元素，是否保证可以插入元素的位置，以便列表仍然保持排序？在使用等于或不使用等于时有效吗？

解决方案

这取决于你如何计算变量 r 。
在你的case

  r = a.size（） 
  

正确的用法是 while（l <= r）

如果计算r为 r = a.size（）; 正确的用法是 while（l< r）

如果没有找到元素，是位置
，其中元素可以插入，以便列表仍然保持
排序？

您没有对您的向量进行排序，对于正确的二进制搜索，向量应在调用二分查找之前排序。

  std :: sort（std :: begin（a），std :: end（a））; 
  

并且标头提供 std :: binary_search ，所以改为重写轮子你可以使用它如下：

  std :: binary_search（std :: begin（a）， std :: end（a），val）; 
  

二进制搜索应返回向量中的索引值，如果找到。但是不能保证它应该提供下一个插入位置。

使用等于或不等于时有效吗？ / p>

我在我的回答的第一部分解释。

I am implementing binary search in C++. Here is my code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int bs(vector<int> a, int val)
{
    int l =0, r = a.size()-1;
    while(l<=r) // Significance of ==
    {
        int mid = l + (r-l)/2;

        if(a[mid]==val) return mid;
        if(a[mid]>val)
        {
            r = mid-1; continue;
        }
        else
        {
            l = mid + 1 ;
        }
    }
   return l; // Deliberately returning this
}

int main()
{
  vector<int> a = {1,3};
  cout << bs(a,1) <<endl;
  return 0;
}

Question 1

In some implementations, I see people use

while(l<r)

while in some they use

while(l<=r)

Is there any conceptual difference between preferring one way ? Any possible sources of error if I don't use == ?

Question 2

In case the element is not found, is l guaranteed to be the position in which the element could be inserted so that the list still remains sorted ? Is this valid while using equal to or not using equal to ?

解决方案

It depends on how you are calculating variable r. In your case

r = a.size()-1;

So correct usage is while(l<=r)

If you calculate r as r = a.size(); correct usage is while(l<r)

In case the element is not found, is l guaranteed to be the position in which the element could be inserted so that the list still remains sorted ?

You didn't sort your vector, for proper binary search, vector should be sorted before calling binary search.

std::sort(std::begin(a),std::end(a));

And header provide a std::binary_search, so instead reinventing the wheel you can use it as follows:

   std::binary_search(std::begin(a),std::end(a),val);

Binary search supposed to return value of index in vector, if it find. But there is no guarantee it should provide the next location for insertion.

Is this valid while using equal to or not using equal to ?

I explained it in first part of my answer.

这篇关于等于二进制搜索的意义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！