Ruby로 바이너리 검색

프로그래밍을 할 때, 우리는 항상 코드 운행의 효율을 고려하고 싶다. 우리는 큰 O 기호를 사용하여 이러한 효율을 논의한다.한 프로그램이 실행되는 효율은 양호한 사용자 체험을 가진 즐거운 사용자와 전혀 사용할 수 없는 응용 프로그램 간의 차이일 수 있다.2진 검색은 우리가 프로그램의 효율을 높일 수 있는 알고리즘 중의 하나다.
2진 검색은 실행 시간 O (log (n) 의 정렬 수조에서 목표의 위치를 찾기 때문에 대수 검색이라고도 부른다.그것은 매번 교체될 때마다 문제를 반으로 나누어 이 점을 실현한다.

이게 도대체 무슨 뜻이야?만약 당신이 전화번호부 한 권을 가지고 있다면, 그 위에 알파벳 순서대로 모든 이름이 열거되어 있으니, 릴리아나가 이 책에 있는지 보고 싶다.전화번호부의 한가운데 부분을 열고 입력한 이름이 당신이 찾는 이름인지, 아니면 알파벳 순서 전이나 그 다음인지 확인하세요.자모표에서 릴리안나보다 훨씬 멀기 때문에, 너는 마커스의 오른쪽에 있는 모든 이름을 포기할 수 있다는 것을 알고 있다.지금 당신은 전화번호부의 시작과 메르세데스 사이의 중점을 선택하고 페르난도에게 착륙하세요.페르난도는 릴리안나에 앞서 페르난도 왼쪽의 모든 이름을 포기했다. 다음 중점은 페르난도와 메르세데스 사이에 있을 것이다.릴리아나를 찾을 때까지, 릴리아나가 전화번호부에 없는 것을 발견할 때까지, 너는 계속 이렇게 하고, 절반의 문제를 검사하고 버려라.
이것은 2진법 검색의 본질로 목표 값과 수조의 중간 요소를 비교한다.만약 그것들이 같지 않다면, 목표가 그 중의 절반에 있을 수 없다는 것을 없애고, 나머지 절반을 계속 검색하고, 중간의 요소를 목표 값과 다시 비교하며, 목표 값을 찾을 때까지 이 동작을 반복한다.검색이 끝났을 때 나머지 절반이 비어 있으면 대상이 그룹에 없습니다.
이런 방법이 선형 스트리밍 수조나 전화번호부에 비해 장점이 있는지 살펴봅시다.
만약 우리가 알파벳순으로 배열된 100개의 이름을 가진 그룹이 있다면만약 내가 하나의 선형 함수로 이름이 존재하는지 검사한다면, 최악의 경우, 나는 몇 번의 검사를 해야 합니까?
100 - 최악의 경우 존재하지 않기 때문에 목록의 모든 이름을 확인했습니다.
만약 내가 전화번호부 방법을 사용한다면, 매번 진열을 반으로 나누면, 나는 몇 번의 검사를 진행합니까?
7 - 50번째 이름을 검사한 다음 25번째, 12번째, 6번째, 3번째, 2번째, 그 다음에 1번 이름을 검사한다.모두 일곱 장의 수표입니다.
그래서 100과 7의 차이는 매우 달콤하다.그러나 100번의 검사는 그다지 나쁘지 않다. 그러나 우리가 진열을 늘리는 데 걸리는 시간은 무엇일까?
스토리지에 200명이 포함된다고 가정합니다.선형 방법에 대해서는 200회 검사를 해야 하지만 전화번호부 검사에는 8회만 하면 된다.400명에게는 400과 9가 될 것으로 보인다.매번 배가 될 때마다 선형 검색의 운행 시간은 배가 되지만 전화번호부 검색의 운행 시간은 한 번 증가한다.우리 그것을 극도로 발휘합시다.만약 우리가 500명의 진열을 가지고 있다면, 우리는 그것을 100배로 늘릴 것이다.전화번호부 검색은 최악의 경우 110회 검사를 진행하지만 선형 검색은 6.43*10^32회 검사가 필요합니다.(그것은 634 노리온이다. 나는 심지어 그것이 숫자인지도 모른다.)우리 은하계의 항성 수량보다 더 많다.이것이 상대적으로 신속하게 완성할 수 있는 알고리즘과 현재 우리 기술이 실현할 수 없는 알고리즘 간의 차이이다.
이제 우리는 이 특정 검색 알고리즘의 중요성을 기본적으로 이해했다. 어떻게 만드는지 보자!
바이너리 검색과 같은 루비 파일을 만들 수 있습니다.rb는 선택한 코드 편집기에서 터미널에서 명령 "rubybinary search.rb"를 실행하여 알고리즘을 실행합니다.

arr_size = 1000
r = Random.new

search_arr = Array.new(arr_size) do
  r.rand(arr_size)
end.sort

search_num = r.rand(arr_size)

우선, 우리는 랜덤수 생성기를 사용하여 1000개의 숫자를 채우고, 이를 정렬합니다. 왜냐하면 이것은 2진법 검색에 필요한 것이기 때문입니다.이러한 방식으로 그룹을 만들고 그것을 사용하여 우리가 검색하고 있는 숫자를 생성합니다. 이 값은 그룹에 있을 수도 있지만, 그룹에 없을 수도 있습니다.이것은 여러 번의 운행 장면을 통해 우리는 최악과 비최악의 장면을 볼 수 있다는 것을 의미한다.
그런 다음 지정된 Rubyindex method를 사용하면 입력된 매개변수와 일치하는 배열의 첫 번째 객체의 인덱스를 반환하고 그렇지 않으면 nil을 반환합니다.우리는 그것에 대해 실제 검사 테스트를 하지 않지만,arr 의 크기를 많이 확대하면, 선형과 2진법의 운행에 필요한 시간의 차이를 볼 수 있다.

puts "Looking for #{search_num}"
puts "Ruby #index O(n)"
resi = search_arr.index(search_num)
puts resi.nil? ? "Could not find #{search_num}" : "Found #{search_arr[resi]} at index #{resi}"

현재, 문제를 끊임없이 둘로 나누면, 우리는 O (lg (n) 가 실행될 때를 얻을 수 있는 교체 2진 검색 방법을 구축할 것이다.

def binary_search_iter(arr, el)
  max = arr.length - 1
  min = 0
end

이 방법은 우리가 찾고 있는 수조와 우리가 찾고 있는 특정한 숫자를 포함하는 두 가지 인자를 포함한다.
우리는 수조의 크기를 반영하기 위해 최대치와 최소치를 설정합니다. 이것은 전화번호부 방법의 오른쪽과 왼쪽을 대표하며, 어느 쪽을 버릴지 선택하는 데 사용됩니다.

def binary_search_iter(arr, el)
  max = arr.length - 1
  min = 0

  while min <= max 
       mid = (min + max) / 2

  end
  return nil
end

최소값과 최대값을 비교하기 위해while 순환을 사용할 수 있습니다. 최소값과 최대값 사이의 크기가 0 또는 마이너스일 경우, 모든 그룹을 훑어보았지만, 원소를 찾지 못했기 때문에 순환을 종료하고 nil로 되돌아갈 것입니다.우리는 중점을 위해 변수를 하나 더 설정해야 한다.Ruby는 정수 제곱법을 사용하는데, 우리는 그것의 장점을 이용할 수 있다. 왜냐하면 그것은 모든 십진수 값을 버리기 때문이다.우리는 수학이 우리가 원하는 정수로 되돌아갈 수 있도록 검사할 수 있다.
그룹 길이가 3이라고 가정하고, 중점은 색인 1에 있습니다.그래서 우리의min=0,max=2,(0+2)/2=1은 예상 지수 1에 중점을 두었다.등장수조에 대해 말하자면, 그것은 좀 까다롭다. 왜냐하면 두 개의 가능한 중점이 있기 때문이다. 우리의 예에서, 우리는 그것이 두 개의 중간 요소 중 하나라면, 어느 중점을 잡느냐에 대해 특별히 관심을 가지지 않는다.만약 우리의 그룹 길이가 3이라면, 우리는 색인 1이나 2가 우리의 중점이기를 바란다.그래서min=0,max=3,(0+3)/2=1은 정수제법이 1.5에서 0.5로 떨어졌기 때문이다.이것은 우리에게 예기한 중점을 주었다.
그리고 중점 색인에 있는 그룹이 우리가 검색하고 있는 숫자와 같은 값을 가지고 있는지 확인할 수 있습니다. 만약 그렇다면,while 순환을 중단하고true로 돌아가기를 원합니다.

def binary_search_iter(arr, el)
  max = arr.length - 1
  min = 0

  while min <= max 
    mid = (min + max) / 2
    if arr[mid] == el
      return mid
    end
  end

  return nil
end

두 가지 논리적인 가능성도 있다.중점은 우리가 검색하고 있는 숫자보다 크거나 작습니다.만약 중점의 숫자가 우리가 찾으려는 요소보다 크다면, 우리는 오른쪽을 무시하고 왼쪽을 주목할 것이다.우리는 최대치를 중점보다 작게 초기화함으로써 이 점을 실현한다.마지막 가능성은mid가 우리가 찾고 있는 요소보다 작기 때문에 왼쪽을 포기하고mid 오른쪽의 요소에 집중해야 한다는 것이다. 우리는min을 현재 중점보다 큰 값으로 리셋함으로써 이를 실현할 수 있다.

def binary_search_iter(arr, el)
  max = arr.length - 1
  min = 0

  while min <= max
    mid = (min + max) / 2
    if arr[mid] == el
      return mid
    elsif arr[mid] > el
      max = mid - 1
    else
      min = mid + 1
    end
  end

  return nil
end

현재 우리는 모든 장면을 논의했다. 만약mid의 값이 요소와 일치한다면, 만약mid로 되돌아갈 것이다. 만약 그것을 찾지 못하면, 우리는nil로 되돌아갈 것이다. 그리고 우리는 순환의 조건을 바꾸어 순환에서 벗어난 위치로 밀어낼 수 있는 문장이 있다.매번 교체할 때마다 최대치를 낮추거나 최소치를 높여 무한순환에 빠지지 않도록 한다.그래서 결국 우리는 순환을 깨고nil로 돌아가거나 중간값으로 돌아갈 것이다.
우리는 이제 2진법으로 검색할 수 있다.

puts "Binary Search Iterative O(lg(n))"
resbi = binary_search_iter(search_arr, search_num)
puts resbi.nil? ? "Could not find #{search_num}" : "Found #{search_arr[resbi]} at index #{resbi}"

이제 루비 2진 검색을 실행할 수 있습니다.rb 터미널에 인쇄된 결과를 보십시오.

지금 우리는 이 두 가지 방법이 모두 정확한 숫자로 되돌아왔다는 것을 볼 수 있다.만약 네가 그것을 운행하는 횟수가 충분하다면, 너는 그것이 숫자를 찾지 못한다는 것을 알게 될 것이다. 최악의 경우는 간혹 발생하는 것이다.선형과 이진 검색 방법이 항상 찾은 숫자의 같은 인덱스로 되돌아오지 않을 수도 있다는 것을 알 수 있습니다.이것은 중복된 숫자가 있기 때문일 수도 있다. 그들은 서로 다른 인덱스에서 이 숫자를 찾았는데, 이것은 무작위 생성기를 사용하는 부작용이다.그것이 다른 색인에 나타날 수 있는 또 다른 이유는 이 두 가지 방법이 수조에서 검색되는 방식이기 때문이다.네가 왼쪽에서 오른쪽으로 다른 선형 수조를 뛰어넘을 때, 너는 그것의 절반을 찾을 수 있다.이것은 내가 위에서 캡처한 두 번째 달리기 때의 상황이다.둘 다 이 숫자를 포함하는 유효한 인덱스를 찾았기 때문에 우리는 인덱스가 아니라 숫자에 관심을 갖는다.
네가 이 프로그램을 실행할 때, 그것은 곧 발생할 것이라는 것을 알아차릴 수 있을 것이다.그러나, 만약 수조의 크기를 200000000으로 늘린다면, 컴퓨터가 선형 함수로 코드를 실행하는 데 더 많은 시간이 걸리지만, 2진법 검색은 여전히 거의 순간적일 것이다.이것은 O (lg (n)) 가 실행될 때이기 때문입니다!
위에서 말한 바와 같이, 우리는 정렬 데이터 집합에 대해 2진법 검색 (문제를 해결하는 전화번호부 방법으로 간주할 수 있다) 을 사용한다. 왜냐하면 O(lg(n))가 선형 검색 O(n)보다 훨씬 빠르기 때문이다.우리는 중점을 찾아서 이 점을 실현하고, 중치가 우리가 검색할 숫자보다 크거나 작은지 여부에 따라 최대치와 최소치를 변경합니다.
보기 편하도록 전체 코드는 다음과 같습니다.

arr_size = 1000
r = Random.new

search_arr = Array.new(arr_size) do
  r.rand(arr_size)
end.sort

search_num = r.rand(arr_size)

def binary_search_iter(arr, el)
  max = arr.length - 1
  min = 0

  while min <= max #know that if the size difference between the min and the max is 0 or negative, we've gone through the whole array and did not find the element
    mid = (min + max) / 2
    if arr[mid] == el
      return mid
    elsif arr[mid] > el #if the mid is greater than element looking for, discount right side and focus on left
      max = mid - 1
    else #covers remaining logic, if mid is less than element looking for, discount left and focus on right
      min = mid + 1
    end
  end

  return nil
end

puts "Looking for #{search_num}"
puts

puts "Ruby #index O(n)"
resi = search_arr.index(search_num)
puts resi.nil? ? "Could not find #{search_num}" : "Found #{search_arr[resi]} at index #{resi}"

puts

puts "Binary Search Iterative O(lg(n))"
resbi = binary_search_iter(search_arr, search_num)
puts resbi.nil? ? "Could not find #{search_num}" : "Found #{search_arr[resbi]} at index #{resbi}"

즐거운 코딩!
리소스:
저자: 미카 슈트