サーチ

• リニアサーチ
• バイナリサーチ
• 応用例：蔵書検索プログラム
• 応用例：自己組織化探索

• 紹介されているサンプルの蔵書検索プログラム（2）（List2-6）がまだ書けていません。

リニアサーチ（線形探索）

基本的な考え方

　とにもかくにも、銭湯から順番に調べて、探しているものが見つかれば、それを返す。

class LinearSearch
  def initialize
    @array = Array.new(20)
    @array.each_index do |i|
      @array[i] = rand(10)
    end
    p @array
  end
  
  def main
    puts "何を探しますか？"
    x = intReader
    r = linearSearch(x)
    
    if r == -1
      puts "#{x}は見つからなかった。"
    else
      puts "#{x}を#{r + 1}番目に発見した。"
    end
  end
  
  private
  def intReader
    gets().to_i
  end
  
  # サーチアルゴリズム
  def linearSearch(x)
    n = 0
    while n < @array.size && @array[n] != x do
      n += 1
    end
    
    return n if n < @array.size
    
    return -1
  end
end

search = LinearSearch.new
search.main

class LinearSearch
  def initialize
    @array = Array.new(20)
    @array.each_index do |i|
      @array[i] = rand(10)
    end
    p @array
  end
  
  def main
    puts "何を探しますか？"
    x = intReader
    r = linearSearch(x)
    
    if r == -1
      puts "#{x}は見つからなかった。"
    else
      puts "#{x}を#{r + 1}番目に発見した。"
    end
  end
  
  private
  def intReader
    gets().to_i
  end
  
  # サーチアルゴリズム
  def linearSearch(x)
    n = 0
    
    # 最後の値を x に入れ替える（番兵をたてる）
    t = @array.pop
    @array.push(x)
    
    # 目的の値を探す
    while @array[n] != x do
      n += 1
    end
    
    # 最後の値を元に戻す
    @array[-1] = t
    
    return n if n < @array.size - 1
    return n if x == t
    return -1
  end
end

search = LinearSearch.new
search.main

●冨倉メモ
　Ruby では、番兵を立てる必要は、あんまりないかも。

バイナリーサーチ

基本的な考え方

1. ソートをかけておく。
2. 全体を2つに分け、目的の値が分割点の前後どちらにあるかを判断する。
3. 上記を繰り返して、目的の値を発見する。

class BinarySearch
  def initialize
    @array = Array.new(20)
    @array.each_index do |i|
      @array[i] = rand(10)
    end
    
    p @array
  end
  
  def main
    # 検索前にソートをしておく必要がある
    puts "並び替え中"
    array = @array.sort
    p array

    puts "何を探しますか？"
    x = intReader
    r = binarySearch(x, array)
    
    if r == -1
      puts "#{x}は見つからなかった。"
    else
      puts "#{x}を#{r + 1}番目に発見した。"
    end
  end
  
  private
  def intReader
    gets().to_i
  end
  
  # サーチアルゴリズム
  def binarySearch(x, array)
    left = 0
    right = array.size - 1
    mid = nil
    
    while left <= right do
      mid = (left + right) / 2
      return mid if array[mid] == x
      
      if array[mid] < x 
        left = mid + 1
      else
        right = mid - 1
      end
    end
    return -1
  end
end

search = BinarySearch.new
search.main

class BinarySearch
  def initialize
    @array = Array.new(20)
    @array.each_index do |i|
      @array[i] = rand(10)
    end
    
    p @array
  end
  
  def main
    # 検索前にソートをしておく必要がある
    puts "並び替え中"
    array = @array.sort
    p array

    puts "何を探しますか？"
    x = intReader
    r = binarySearch(x, array)
    
    if r == -1
      puts "#{x}は見つからなかった。"
    else
      puts "#{x}を#{r + 1}番目に発見した。"
    end
  end
  
  private
  def intReader
    gets().to_i
  end
  
  # サーチアルゴリズム
  def binarySearch(x, array)
    left = 0
    right = array.size - 1
    mid = nil
    
    while left < right do
      mid = (left + right) / 2
      if array[mid] < x 
        left = mid + 1
      else
        right = mid
      end
    end
    
    return left if array[left] == x
    return -1
  end
end

search = BinarySearch.new
search.main

応用例：蔵書検索プログラム

class Book
  attr_reader :title, :author, :bookID, :available
  
  def initialize( title, author, bookID, available )
    @title = title
    @author = author
    @bookID = bookID
    @available = available
  end
end

class SearchBook
  def initialize
    @bookArray = Array.new()
  end
  
  def main()
    initDate()
    sortBook(0, @bookArray.size - 1, @bookArray)
    
    while true do
      puts "検索する本のIDを入力して下さい。"
      puts "（終了する場合は 0 を入力）"
      key = intReader()
      break if key == 0
      position = searchBook(@bookArray, key)
      if position != -1
        puts "---------- 次の本が見つかりました。"
        puts "[Title] : #{@bookArray[position].title}"
        puts "[Author]: #{@bookArray[position].author}"
        if @bookArray[position].available
          puts "この本は貸し出し可能です"
        else
          puts "この本は貸出中です"
        end
      else
        puts "お探しの本は見つかりませんでした"
      end
    end
  end
  
  private
  def intReader
    gets().to_i
  end
  
  def searchBook( books, key )
    left = 0
    mid = nil
    right = books.size - 1
    
    while left < right do
      mid = (left + right) / 2
      if books[mid].bookID < key
        left = mid + 1
      else
        right = mid
      end
    end
    return left if books[left].bookID == key
    return -1
  end
  
  def initDate()
    @bookArray[0] = Book.new("book0", "author0", 1000, true)
    @bookArray[1] = Book.new("book1", "author1", 502, false)
    @bookArray[2] = Book.new("book2", "author2", 731, false)
    @bookArray[3] = Book.new("book3", "author3", 628, true)
    @bookArray[4] = Book.new("book4", "author4", 1, true)
  end
  
  def sortBook( bottom, top, books )
    lower = bottom
    upper = top
    div = nil
    
    return if bottom >= top
    
    # 適当な基準を選択
    div = books[bottom].bookID
    while lower < upper do
      while books[lower].bookID < div do
        lower += 1
      end
      while books[upper].bookID > div do
        upper -= 1
      end
      
      if lower < upper
        temp = books[lower]
        books[lower] = books[upper]
        books[upper] = temp
        lower += 1
        upper -= 1
      end
    end
    sortBook(bottom, upper, books)
    sortBook(upper + 1, top, books)
  end
end

searchBook = SearchBook.new
searchBook.main

応用例：自己組織化探索

基本的な考え方

　一致した値を配列の先頭に持ってくることで、次回以降の検索を素早く行う。全体の中で一部の値だけが何度も検索される場合に有効。

　参考：リスト「自己組織化探索」

class OrganizationSearch
  def initialize
    @array = Array.new(20)
    @array.each_index do |i|
      @array[i] = rand(20)
    end
  end
  
  def main
    while true
      p @array
      puts "何を探しますか？ [-1 で終了]"
      x = intReader
      if x == -1
        break
      end
      
      r = organizationSearch(x, @array)
      if r == -1
        puts "見つかりません"
      else
        puts "#{x} は #{r} 番目です"
      end
    end
  end
  
  private
  def intReader
    gets().to_i
  end
  
  def organizationSearch(x, a)
    n = 0
    while (n < a.size && a[n] != x)
      n += 1
    end
    
    if n < a.size
      if n > 0
        t = a[n - 1]
        a[n - 1] = a[n]
        a[n] = t
        return n - 1
      end
      return n
    end
    return -1
  end
end

o = OrganizationSearch.new
o.main