Проблема с алгоритмом бинарного поиска в ruby - PullRequest
Новая
       7

Проблема с алгоритмом бинарного поиска в ruby

0 голосов
/ 03 марта 2011 
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

Ответы [ 2 ]

5 голосов
/ 04 марта 2011

Это добавляет бинарный поиск ко всем массивам: 

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
0 голосов
/ 04 марта 2011

stringarray, который передается вашей функции, на самом деле не массив строк, а просто простая строка.Использование метода [] в строке возвращает код символа в заданной позиции в виде Fixnum;поэтому stringarray [k] возвращает код символа в позиции k в строке.И, как говорится в сообщении об ошибке, Fixnum не имеет include?.

Даже если stringarray был массивом строк, я не уверен, почему вы бы сравнили строки с include?.include? для выяснения, существуют ли элементы в массиве.Чтобы сравнить строки, просто используйте ==.

...