탐색법이란?

이번은 기본적인 이야기이므로 배열로 생각합니다. 배열 안에 있는 요소가 처음부터 몇번째인지를 확인할까? ... 네, 거기 당신! 그런 때는 탐색법 사용합시다! !

토마 뉘앙스는 이런 느낌입니다

선형 탐색 방법(linear_search)

배열의 첫 번째 요소부터 순서대로 내용을 확인합니다. 모두가 한 적이 있습니다.

linear_search.rb

def linear_search(nums, aim)
  nums.each_with_index do |item, index|
    return index if aim == item
  end
end

nums = [5, 3, 7, 4, 6]
aim = 7
hit = linear_search(nums, aim)
p "nums: #{nums}" # "nums: [5, 3, 7, 4, 6]"
p "aim: #{aim}, index: #{hit}" # "aim: 7, index: 2"

이진 검색법(binary_search)

절반씩 점검합니다. 주의점은 배열의 요소가 작은 값으로부터 큰 값에 깨끗이 늘어서 있을 필요가 있는 것이군요.

binary_search.rb

def binary_search(nums, aim)
  nums_head = 0
  nums_tail = nums.size - 1
  while nums_head <= nums_tail
    nums_center = (nums_tail + nums_head) / 2
    case nums[nums_center] <=> aim
    when -1
      nums_head += 1
    when 0
      return nums_center
    else
      nums_tail -= 1
    end
  end
end

nums = [5, 3, 7, 4, 6].sort
aim = 7
hit = binary_search(nums, aim)
p "nums: #{nums}" # "nums: [3, 4, 5, 6, 7]"
p "aim: #{aim}, index: #{hit}" # "aim: 7, index: 4"

해시 탐색 방법

결정된 규칙으로 저장하고 그 규칙을 바탕으로 내용을 찾습니다. 이것은 상당히 복잡하기 때문에 이 기사의 마지막에 실는 책등에서 공부하면 좋을지도. 인터넷에도 여러 가지가 있습니다

hash_search.rb

def hash_init(nums)
  hashes = []
  hashes = Array.new(nums.size * 2, 0)
  nums.each do |num|
    k = num % hashes.size
    while_count = 0
    while hashes[k] != 0 || while_count < hashes.size
      k = (k+1) % hashes.size
      while_count += 1
    end
    hashes[k] = num
  end
  hashes
end

def hash_search(nums, aim)
  hashes = hash_init(nums)
  p "hashes: #{hashes}"
  k = aim % hashes.size
  hashes.size.times do
    case hashes[k]
    when 0
      return nil
    when aim
      return k
    else
      k = (k+1) % hashes.size
    end
  end
end

nums = [12, 25, 36, 20, 30, 8, 42]
aim = 36
hit = hash_search(nums, aim)
p "nums: #{nums}" # "nums: [3, 4, 5, 6, 7]"
p "aim: #{aim}, index: #{hit}" # "aim: 7, index: 4"

요약

자세한 내용은이 책에 실려 있기 때문에 추천 해요! 언뜻 보면 초보자를위한 일러스트 풍부한 내용이없는 책처럼 보이지만 내용은 확고했습니다. 언어를 결정하고 코드를 쓰는 것은 아니기 때문에 어떤 언어를 사용하는 사람이라도 읽기 쉬운 한 권이었습니다.
htps //w w. 아마존. 이. jp/dp/B01CZD 치네/레 f=dp-킨 dぇ-레아레 ct? _엔코엔 g=우 TF8&btkr=1

덤

클래스에 넣었을 뿐.

search.rb

class Search
  def initialize(nums, aim)
    @nums = nums
    @aim = aim
  end
  def linear_search
    @nums.each_with_index do |item, index|
      return index if @aim == item
    end
  end

  def binary_search
    nums_head = 0
    nums_tail = @nums.size - 1
    while nums_head <= nums_tail
      nums_center = (nums_tail + nums_head) / 2
      case nums[nums_center] <=> @aim
      when -1
        nums_head += 1
      when 0
        return nums_center
      else
        nums_tail -= 1
      end
    end
  end

  def hash_init(nums)
    hashes = []
    hashes = Array.new(nums.size * 2, 0)
    nums.each do |num|
      k = num % hashes.size
      while_count = 0
      while hashes[k] != 0 || while_count < hashes.size
        k = (k+1) % hashes.size
        while_count += 1
      end
      hashes[k] = num
    end
    hashes
  end

  def hash_search
    hashes = hash_init(@nums)
    p "hashes: #{hashes}"
    k = @aim % hashes.size
    hashes.size.times do
      case hashes[k]
      when 0
        return nil
      when @aim
        return k
      else
        k = (k+1) % hashes.size
      end
    end
  end
end

p nums = [12, 25, 36, 20, 30, 8, 42]
aim = 36
search = Search.new(nums, aim)
hit = search.hash_search
p "aim: #{aim}, hit: #{hit}"

추가 (2018/11/08)

코멘트에서 지적해 주신 내용<@scivola님>에서, 제가 몰랐던 편리한 메소드등이 있었으므로 이쪽에 기재하겠습니다.

while 는 nil 를 돌려준다...메소드의 반환값은 그 메소드내에서의 마지막 처리입니다만, 반복이 그 마지막 처리의 경우는 nil 를 돌려주는 것 같습니다.

Array.new(num, 0) ... 배열을 만들 때 미리 정해진 요소수(num)에 모두0를 넣고 싶다면 이 일행으로 만들 수 있는 것 같습니다. 반복을 사용하는 것보다 코드가 가벼워지기 때문에 적극적으로 사용해 가고 싶네요.

Numeric#<=> ... 2 개의 값의 관계를 -1, 0, 1, nil로 나타내 주는 우수한 것.