바이너리 검색 자바스크립트

Michael Zippo

자바스크립트에서 바이너리 검색을 코딩하는 방법

검색 알고리즘은 프로그래머의 삶을 크게 촉진합니다. 이렇게 하면 수십, 수백 또는 수천 개의 항목으로 구성된 데이터세트에서 특정 항목을 더 쉽게 찾을 수 있습니다.

가장 널리 사용되는 검색 형식 중 하나는 이진 검색입니다. 이 검색은 배열에서 요소를 빠르게 찾습니다. 검색에서 항목을 검사할 때마다 찾을 항목의 수가 절반으로 줄어듭니다.

이 가이드에서는 이진 검색이 무엇이며 어떻게 작동하는지 설명합니다. 다음으로 반복 및 재귀의 두 가지 접근 방식을 사용하여 이진 검색을 구현하는 방법을 알아보겠습니다.

이진 검색이란 무엇입니까?

이진 검색은 정렬된 배열에서 요소를 검색하는 컴퓨터 알고리즘입니다.

배열의 중간에서 시작하여 중간 요소가 찾고 있는 숫자보다 작거나 같거나 큰지 확인합니다.

숫자가 작으면 알고리즘 더 작은 숫자가 있는 배열의 왼쪽 절반을 계속 찾는 방법을 알고 있습니다. 숫자가 더 크면 알고리즘은 배열의 오른쪽 절반에 초점을 맞춥니다. 이진 검색은 순서가 지정된 목록에서만 작동합니다.

이진 검색은 선형 검색보다 더 효율적입니다. 실제로 검색을 수행할 때마다 목록에 남아 있는 항목의 수가 절반으로 줄어듭니다.

바이너리 검색 사용 방법

이진 검색은 일단 배우면 이해하기 쉽습니다.

이진 검색 알고리즘을 구현하기 전에 검토해 보겠습니다. 목록에서 숫자 " 9 "를 찾을 수 있습니다. 순서가 있는 목록부터 시작하겠습니다.

6 < / td>

먼저, 우리는 중간 숫자를 찾아 변수에 할당해야 합니다. 이것은 첫 번째 숫자와 마지막 숫자의 합을 계산하고 2로 나누어 구합니다. 이 "중앙" 변수를 다음과 같이 부를 것입니다.

시작	< br>	중간		끝
2	6	8	9	10

8은 평균입니다. 따라서 중심 번호를 찾고 있는 번호와 비교할 수 있습니다. 중심 번호가 찾고 있는 번호와 같으면 검색이 중지될 수 있습니다.

이 예에서 8은 9와 같지 않습니다. 검색은 계속됩니다.

그래서 중간에 있는 숫자가 9보다 큰지 비교해야 합니다. 그렇지 않습니다.

이는 우리가 찾고 있는 숫자가 중앙 뒤에 있어야 함을 알려줍니다. 숫자입니다. 9는 정렬된 목록에서 8보다 큽니다. 시작 숫자를 중앙 숫자와 같게 설정하십시오. 이것은 우리가 찾고 있는 숫자가 중앙 숫자 앞에 오지 않는다는 것을 알고 있기 때문입니다.

만약 우리가 찾고 있는 숫자가 더 아기라면, 우리는 마지막 숫자를 중간 숫자와 같게 설정할 것입니다. 숫자가 중간 숫자보다 작기 때문에 우리는 목록의 하단 절반에 검색을 집중할 수 있습니다.

9가 8보다 크므로 목록의 위쪽 절반에서 이진 검색이 다시 반복됩니다.

< td> 중간

시작 끝

8 < /td>

중심 수를 구합시다. 그것은 9입니다. 우리는 9를 우리가 찾고 있는 숫자와 비교할 수 있습니다. 9는 우리가 찾고 있는 숫자와 같습니다.

이는 우리의 연구가 중단될 수 있음을 의미합니다. 목록에서 9번을 찾았습니다!

JavaScript에서 이진 검색을 구현하는 방법

이진 검색은 반복 또는 재귀 접근 방식을 사용하여 구현할 수 있습니다.

반복 이진 검색

반복 이진 검색은 while 루프를 사용하여 목록에서 항목을 찾습니다. 이 루프는 목록에서 항목을 찾거나 목록을 검색할 때까지 실행됩니다.

함수 이진 검색을 수행합니다.

시작과 끝이라는 두 개의 변수를 정의하는 것으로 시작하겠습니다. 이것들은 우리의 연구에서 가장 높은 값과 가장 낮은 값을 추적합니다. 시작 번호가 끝 번호보다 클 때까지 실행되는 while 루프 를 사용합니다. 이 루프는 목록의 시작과 끝 사이의 중간 숫자를 계산합니다.

찾고 있는 숫자가 중간에 있는 숫자와 같으면 중간에 있는 숫자가 메인 프로그램으로 돌아갑니다. 숫자가 작을수록 시드 값은 중간 숫자에 1을 더한 값과 같도록 설정됩니다. 이러한 비교는 if 문 을 사용하여 수행됩니다.

그렇지 않으면 마지막 숫자는 중간 숫자에서 1을 뺀 값으로 설정됩니다. while 루프를 실행한 후 숫자를 찾지 못하면 -1을 반환합니다. 이를 기본 조건이라고 합니다. 주 프로그램에서 우리는 반환된 숫자가 -1인지 확인합니다. 즉, 숫자를 찾을 수 없다는 의미입니다.

우리 함수는 아직 작동하지 않습니다. 이름을 지정하는 기본 프로그램을 작성해야 합니다.

검색할 숫자 목록과 목록에서 찾고자 하는 숫자를 정의했습니다. 다음으로 binarySearch 함수를 호출했습니다. 이것은 우리의 연구를 할 것입니다. 검색은 -1 또는 찾고 있는 요소의 위치를 반환합니다.

-1은 항목을 찾을 수 없음을 나타냅니다. 요소가 발견되지 않으면 else 문의 내용이 실행됩니다. 그렇지 않으면 if 문의 내용이 실행됩니다.

코드를 실행해 보겠습니다.

이는 검색이 성공했음을 알려줍니다!