기본적인 검색인 순차 검색과 색인 순차 검색은 구현하지 않았다.
이진 검색도 이론은 누구나 알 만한 것이므로 Pseudocode 와 설명을 생략한다.
소스 >>
# 이진 검색 구현
# 2009-03-18, Jung-taek Lim(Heart)
def make_example_array
array = [2, 8, 10, 16, 22, 30, 31, 69]
end
def print_array(array)
puts array.map {|x| x.to_s + " "}.to_s
end
def binary_search(arr, low, high, value)
# 초기값 바운더리 체크 포함
return -1 if low < 0 || high >= arr.length || low > high
middle = (low + high) / 2
return middle if arr[middle] == value
return binary_search(arr, low, middle - 1, value) if arr[middle] > value
# if arr[middle] < value
return binary_search(arr, middle + 1, high, value)
end
array = make_example_array
# 실제 있는 값을 테스트
puts "30's idx : " + binary_search(array, 0, array.length - 1, 30).to_s
puts "2's idx : " + binary_search(array, 0, array.length - 1, 2).to_s
puts "69's idx : " + binary_search(array, 0, array.length - 1, 69).to_s
# 바운더리 내에 없는 값을 테스트
puts "1's idx : " + binary_search(array, 0, array.length - 1, 1).to_s
puts "80's idx : " + binary_search(array, 0, array.length - 1, 80).to_s
puts "9's idx : " + binary_search(array, 0, array.length - 1, 9).to_s
|
결과 >>
30's idx : 5
2's idx : 0
69's idx : 7
1's idx : -1
80's idx : -1
9's idx : –1
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| Divide & Conquer : 거듭제곱 알고리즘 (0) | 2009/05/06 |
|---|---|
| 해시 검색 - in Ruby (0) | 2009/03/18 |
| 이진 검색 - in Ruby (0) | 2009/03/18 |
| 트리 정렬 - in Ruby (0) | 2009/03/18 |
| 힙 정렬 - in Ruby (0) | 2009/03/18 |
| 기수 정렬 - in Ruby (0) | 2009/03/18 |
