Ruby 2 분 검색(2 분 검색)알고리즘 을 구현 하 는 간단 한 예제

컴퓨터 과학 에서 2 분 검색(영어:binary search)은 반절 검색(영어:half-interval search),대수 검색(영어:logarithmic search)이 라 고도 부 르 며 질서 있 는 배열 에서 특정한 요 소 를 찾 는 검색 알고리즘 입 니 다.검색 과정 은 배열 의 중간 요소 부터 시작 합 니 다.중간 요소 가 찾 아야 할 요소 라면 검색 과정 이 끝 납 니 다.만약 에 특정한 요소 가 중간 요소 보다 크 거나 작 으 면 배열 이 중간 요소 보다 크 거나 작은 절반 에서 찾 고 시작 과 같이 중간 요소 부터 비교 합 니 다.어떤 단계 에서 배열 이 비어 있 으 면 찾 을 수 없다 는 뜻 이다.이런 검색 알고리즘 은 매번 비교 할 때마다 검색 범 위 를 절반 으로 축소 시킨다.
복잡 도 분석
시간 복잡 도:
반절 수색 은 매번 검색 구역 을 절반 으로 줄 이 고 시간 복잡 도 는이다.(n 집합 원소 의 개 수 를 나타 낸다)
공간 복잡 도:
재 귀 형식 으로 정의 되 지만 재 귀 는 순환 으로 바 꿀 수 있다.
Ruby 코드 예시

def binseaech(arr, i)
  low, high = 0, arr.size - 1
  while (low < high)
    mid = (low + high)/2
    if arr[mid] < i
      low = mid + 1
    elsif arr[mid] > i
      high = mid - 1
    else
      return mid
    end
  end
end

arr = [1,3,12,34,35,46,91,108]
puts binseaech(arr, 91)

결과:

6
[Finished in 0.1s]