차례:
정의-이진 검색이란 무엇입니까?
이진 검색 알고리즘은 정렬 된 배열에 포함 된 특정 값의 위치를 찾는 데 사용됩니다. 나누기와 정복의 원리를 사용하여이 검색 알고리즘은 매우 빠를 수 있지만 데이터는 정렬 된 형식이어야합니다. 배열의 중간에서 검색을 시작하고 시퀀스의 첫 번째 아래쪽 또는 위쪽 절반으로 내려 가면서 작동합니다. 중앙값이 목표 값보다 낮 으면 검색이 더 높아야한다는 의미입니다. 그렇지 않은 경우 배열의 내림차순 부분을 찾아야합니다.
이진 검색은 반 구간 검색 또는 로그 검색이라고도합니다.
Techopedia는 이진 검색을 설명합니다
이진 검색은 일련의 주문 된 항목에서 특정 대상 값을 찾는 빠르고 효율적인 방법입니다. 정렬 된 목록의 중간에서 시작하여 대상 값과 비교 한 중간 값을 기준으로 목록을 오름차순 또는 내림차순으로 결정함으로써 검색 공간을 반으로 효과적으로 줄일 수 있습니다.
예를 들어, 목표 값이 8이고 검색 공간이 1-11 인 경우
- 중앙값 / 중간 값이 발견되고 포인터가 여기에 설정됩니다 (이 경우 6).
- 8의 목표는 6과 비교됩니다. 6이 8보다 작기 때문에 목표는 상위 절반에 있어야합니다.
- 포인터가 다음 값 (7)으로 이동하고 대상과 비교됩니다. 더 작으므로 포인터가 다음으로 높은 값으로 이동합니다.
- 포인터가 8에 있습니다. 이것을 대상과 비교하면 정확히 일치하므로 대상을 찾았습니다.
이진 검색을 사용하면 대상을 세 값만 비교하면됩니다. 선형 검색과 비교할 때 첫 번째 값에서 시작하여 위로 이동하여 대상을 8 개의 값과 비교해야합니다. 이진 검색은 순서가 지정된 데이터 집합에서만 가능합니다. 데이터가 무작위로 배열되면 선형 검색은 항상 결과를 산출하지만 이진 검색은 무한 루프에 빠질 수 있습니다.
