이진 검색: 검색 속도를 높이십시오!

내장 메서드를 사용하지 않고 아래 배열에 15가 있는지 확인해야 한다고 가정해 보겠습니다. 어떻게 하시겠습니까?

array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]

한 가지 방법은 배열의 각 값을 살펴보고 15와 같은지 확인하고 같으면 true를 반환하는 것입니다. 이 같은:

for i in 0...array.length do
   if array[i] == search
        return true
   end
end

충분히 쉽습니다. 그러나 선형 검색은 O(N)의 최악의 시간 복잡도를 가지며, 이는 최악의 시나리오(예: 21 또는 10과 같이 존재하지 않는 값을 찾고 있다고 가정)에서 모든 단일 요소를 비교해야 함을 의미합니다. .

11개 항목의 배열에는 그다지 나쁘지 않지만 100M 값 길이인 경우에는 좋지 않습니다. 그것은 1억개의 잠재적인 비교입니다!

이진 검색을 입력합니다. 매우 강력하여 최대 27번의 비교에서 100M 길이 배열의 모든 값을 찾습니다. 어때요?

배열의 주요 특징은 이미 정렬되어 있다는 것입니다. 중간 값을 선택하면 왼쪽의 모든 것이 작거나 같고 오른쪽의 모든 것이 크거나 같음을 알 수 있습니다.

array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
# middle value is 11

15를 검색하는 경우 중간점 11과 한 번 비교할 수 있습니다. 15는 11보다 크므로 배열의 왼쪽 절반을 볼 필요가 없으므로 검색을 즉시 반으로 줄일 수 있습니다. 그런 다음 13에서 새 검색을 시작하고 새 중간점을 찾을 수 있습니다.

이진 검색은 비교할 때마다 검색 목록을 절반으로 줄이기 위해 배열이 정렬된다는 사실을 사용합니다. 엄청나네요!

의사 코드

검색 시작 및 검색 종료 변수 설정

검색 영역이 유효한 동안(예: 시작이 종료보다 작거나 같음)

시작과 끝 사이의 중간점 인덱스를 설정합니다

.

해당 중간점 인덱스의 값을 검색 값과 비교합니다

.

동등하다면 훌륭합니다! 중간점을 반환할 수 있습니다

.

중간점 값이 검색보다 높으면 종료 인덱스를 중간점 앞의 인덱스로 설정합니다

.

중간점 값이 검색보다 낮으면 시작 인덱스를 중간점 이후의 값으로 설정합니다

.

값이 없으면 검색 영역이 결국 유효하지 않게 되고 false를 반환합니다

.

반복적인 루비 코드

이것을 반복적으로 풀면 코드는 다음과 같습니다.

def binarySearch(array, search)
  start = 0
  finish = (array.length) - 1

  while start <= finish
    midpoint = (start + finish) / 2
    if array[midpoint] == search
      return midpoint
    elsif array[midpoint] > search
      finish = midpoint - 1
    elsif array[midpoint] < search
      start = midpoint + 1
    end
  end
  return false
end

재귀 루비 코드

같은 논리를 사용하여 이것을 재귀적으로 작성할 수도 있습니다. 좀 더 깨끗하다고 ​​생각하지만 더 많은 메모리를 사용하므로 시작/종료 변수를 인수로 전달해야 합니다.

def binarySearchRecursive(array, search, start, finish)
  if finish < start
    return false
  end
  midpoint = (start + finish) / 2
  if array[midpoint] == search
    return midpoint
  elsif array[midpoint] > search
    binarySearchRecursive(array, search, start, midpoint - 1)
  elsif array[midpoint] < search
    binarySearchRecursive(array, search, midpoint + 1, finish)
  end
end

그리고 그것은 이진 검색입니다! 이 정보가 유용하거나 흥미롭기를 바라며, 다음에 100M의 강력한 건초 더미에서 바늘을 찾아야 할 때 시간을 절약할 수 있기를 바랍니다.