草庐IT

c++ - BinarySearch 返回它所属位置的索引

coder 2024-02-21 原文

所以我想写一个代码来返回键所在的索引，或者如果它不存在，它应该在哪里。我错过了什么？ min 为 0，max 为 size - 1，buf 已排序

int binarySearch(string buf[], string key, int min, int max){

int mid;
while (max >= min){
    mid = (min + max) / 2;

    if (buf[mid] < key)
        min = mid + 1;
    else if (buf[mid] > key)
        max = mid - 1;

    else
        return mid;

}
return min;
}

最佳答案

我实际上遇到了同样的问题，所以我写了这个通用代码(也许你可能想使用与 std 不同的命名空间；))下面的代码返回一个迭代器到序列中小于或的最大元素等于值。它使用 O(N log N) 时间 N = std::difference(first, last)，假设 O(1) 随机访问 [first ... last]。

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

namespace std {

template<class RandomIt, class T>
RandomIt binary_locate(RandomIt first, RandomIt last, const T& val) {
  if(val == *first) return first;
  auto d = std::distance(first, last);  
  if(d==1) return first;
  auto center = (first + (d/2));
  if(val < *center) return binary_locate(first, center, val);
  return binary_locate(center, last, val);
}  

}

int main() {
    std::vector<double> values = {0, 0.5, 1, 5, 7.5, 10, 12.5};
    std::vector<double> tests = {0, 0.4, 0.5, 3, 7.5, 11.5, 12.5, 13};
    for(double d : tests) {
        auto it = std::binary_locate(values.begin(), values.end(), d);
        std::cout << "found " << d << " right after index " << std::distance(values.begin(), it) << " which has value " << *it << std::endl;
    }
    return 0;
}

来源:http://ideone.com/X9RsFx

代码非常通用，它接受 std::vectors、std::arrays 和数组，或任何允许随机访问的序列。假设(读取前提条件)是 val >= *first 并且值 [first, last) 已排序，如 std::binary_search 所需。

请随意提及我使用过的错误或不当行为。

关于c++ - BinarySearch 返回它所属位置的索引，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19603975/

BinarySearchampfirstsectionltc++sortingbinary-search-tree

有关c++ - BinarySearch 返回它所属位置的索引的更多相关文章

  1. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  4. ruby - Ruby 中的隐式返回值是怎么回事？ - 2

    所以我开始关注ruby​​，很多东西看起来不错，但我对隐式return语句很反感。我理解默认情况下让所有内容返回self或nil但不是语句的最后一个值。对我来说，它看起来非常脆弱(尤其是)如果你正在使用一个不打算返回某些东西的方法(尤其是一个改变状态/破坏性方法的函数!)，其他人可能最终依赖于一个返回对方法的目的并不重要，并且有很大的改变机会。隐式返回有什么意义？有没有办法让事情变得更简单？总是有返回以防止隐含返回被认为是好的做法吗？我是不是太担心这个了？附言当人们想要从方法中返回特定的东西时，他们是否经常使用隐式返回，这不是让你组中的其他人更容易破坏彼此的代码吗？当然，记录一切并给出

  5. ruby-on-rails - ruby 日期方程不返回预期的真值 - 2

    为什么以下不同？Time.now.end_of_day==Time.now.end_of_day-0.days#falseTime.now.end_of_day.to_s==Time.now.end_of_day-0.days.to_s#true 最佳答案 因为纳秒数不同:ruby-1.9.2-p180:014>(Time.now.end_of_day-0.days).nsec=>999999000ruby-1.9.2-p180:015>Time.now.end_of_day.nsec=>999999998

  6. ruby - 从 String#split 返回的零长度字符串 - 2

    在Ruby1.9.3(可能还有更早的版本，不确定)中，我试图弄清楚为什么Ruby的String#split方法会给我某些结果。我得到的结果似乎与我的预期相反。这是一个例子:"abcabc".split("b")#=>["a","ca","c"]"abcabc".split("a")#=>["","bc","bc"]"abcabc".split("c")#=>["ab","ab"]在这里，第一个示例返回的正是我所期望的。但在第二个示例中，我很困惑为什么#split返回零长度字符串作为返回数组的第一个值。这是什么原因呢？这是我所期望的:"abcabc".split("a")#=>["bc"

  7. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  8. ruby - 为什么 Integer.respond_to?( :even? ) 返回 false？ - 2

    我一直在研究RubyKoans，我发现about_open_classes.rbkoan很有趣。特别是他们修改Integer#even?方法的最后一个测试。我想尝试一下这个概念，所以我打开了Irb并尝试运行Integer.respond_to?(:even?)，但令我惊讶的是我得到了错误。然后我尝试了Fixnum.respond_to?(:even?)并得到了错误。我还尝试了Integer.respond_to?(:respond_to?)并得到了true，当我执行2.even?时，我也得到了true。我不知道发生了什么。谁能告诉我缺少什么？ 最佳答案

  9. ruby - 正则表达式在哪个位置失败？ - 2

    我需要一个非常简单的字符串验证器来显示第一个符号与所需格式不对应的位置。我想使用正则表达式，但在这种情况下，我必须找到与表达式相对应的字符串停止的位置，但我找不到可以做到这一点的方法。(这一定是一种相当简单的方法……也许没有？)例如，如果我有正则表达式:/^Q+E+R+$/带字符串:"QQQQEEE2ER"期望的结果应该是7 最佳答案 一个想法:你可以做的是标记你的模式并用可选的嵌套捕获组编写它:^(Q+(E+(R+($)?)?)?)?然后你只需要计算你获得的捕获组的数量就可以知道正则表达式引擎在模式中停止的位置，你可以确定匹配结束

  10. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

随机推荐