ruby中的二分查找算法问题

发布于 2024-10-20 08:06:44 字数 883 浏览 3 评论 0原文

def binarysearch(a, b,  tofind, stringarray)
  k=(a+b)/2
  if a==b
    return nil
  end
  if (stringarray[k]).include? tofind
    return stringarray[k]
  end
  if (stringarray[k]<=>tofind)==1
    binarysearch(a,k,tofind,stringarray)
  end
  if (stringarray[k]<=>tofind)==-1
    binarysearch(k,b,tofind,stringarray)
  end
  if (stringarray[k]<=>tofind)==0
    return stringarray[k]
  end
end

这是一种二分查找算法。 a 和 b 是它正在处理的数组索引，tofind 是它正在搜索的字符串，stringarray 是字符串数组。不幸的是，每次我尝试运行这个函数时，我都会收到以下语法错误：

undefined method `include?' for 1:Fixnum (NoMethodError)`

但这不是一个修复号。我对 Ruby 还很陌生，所以我很容易会错过一些明显的东西。有什么建议吗？

这是我声明 stringarray 的地方：（Netbeans 说它是一个数组）

  strings=Array.new
  newstring=""
  until newstring=="no" do
    newstring=gets.chomp
    strings[strings.size]=newstring
  end

原文

def binarysearch(a, b,  tofind, stringarray)
  k=(a+b)/2
  if a==b
    return nil
  end
  if (stringarray[k]).include? tofind
    return stringarray[k]
  end
  if (stringarray[k]<=>tofind)==1
    binarysearch(a,k,tofind,stringarray)
  end
  if (stringarray[k]<=>tofind)==-1
    binarysearch(k,b,tofind,stringarray)
  end
  if (stringarray[k]<=>tofind)==0
    return stringarray[k]
  end
end

This is a binary search algorithm. The a and b are the array indices that it is working on, tofind is a string that it is searching for, and stringarray is an array of strings. Unfortunately, every time that I try to run this function I get the following syntax error:

undefined method `include?' for 1:Fixnum (NoMethodError)`

But this is not a fixnum. I am pretty new to Ruby, so I could easily be missing something obvious. Any advice?

This is where I declare stringarray: (Netbeans says that it is an array)

  strings=Array.new
  newstring=""
  until newstring=="no" do
    newstring=gets.chomp
    strings[strings.size]=newstring
  end

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

桃气十足 2024-10-27 08:06:44

这将为所有数组添加二分搜索：

class Array
  def binarysearch(tf,lower=0,upper=length-1)
    return if lower > upper
    mid = (lower+upper)/2
    tf < self[mid] ? upper = mid-1 : lower = mid+1
    tf == self[mid] ? mid : binarysearch(tf,lower,upper)
  end
end

然后您可以像这样使用它：

(0..100).to_a.binarysearch(25)
=> 25
(0..100).to_a.binarysearch(-1)
=> nil

或者从一开始就指定您的下限和上限：

(0..100).to_a.binarysearch(25, 50, 100)
=> nil

This adds binary search to all arrays:

class Array
  def binarysearch(tf,lower=0,upper=length-1)
    return if lower > upper
    mid = (lower+upper)/2
    tf < self[mid] ? upper = mid-1 : lower = mid+1
    tf == self[mid] ? mid : binarysearch(tf,lower,upper)
  end
end

Then you can use it like this:

(0..100).to_a.binarysearch(25)
=> 25
(0..100).to_a.binarysearch(-1)
=> nil

Or specify your lower and upper bound from the beginning:

(0..100).to_a.binarysearch(25, 50, 100)
=> nil

回复收藏 0 原文

情话已封尘 2024-10-27 08:06:44

传递给函数的 stringarray 实际上并不是字符串数组，而只是一个简单的字符串。对字符串使用 [] 方法返回给定位置处字符的字符代码，作为 Fixnum；所以 stringarray[k] 返回字符串中位置 k 的字符的字符代码。正如错误所示，Fixnum 没有 include?。

即使 stringarray 是一个字符串数组，我也不确定为什么要与 include? 进行字符串比较。 include? 用于查找数组中是否存在项目。要比较字符串，只需使用==。