이진 검색 알고리즘: 기능, 이점, 시간 및 공간 복잡성

소개

모든 계산 시스템에서 검색은 개발해야 할 가장 중요한 기능 중 하나입니다. 검색 기술은 파일 검색, 인덱싱 및 기타 여러 응용 프로그램에서 사용됩니다. 많은 검색 기술을 사용할 수 있습니다. 그 중 하나는 이진 검색 기술입니다.

이진 검색 알고리즘 은 모든 반복에서 목록의 절반을 무시한다는 아이디어에서 작동합니다 . 주어진 목록에서 찾고 있는 값을 찾을 때까지 목록을 계속 분할합니다. 이진 검색 알고리즘 은 간단한 선형 검색 알고리즘으로 빠르게 업그레이드됩니다.

코딩 경험이 필요하지 않습니다. 360° 경력 지원. IIIT-B 및 upGrad에서 기계 학습 및 AI PG 디플로마.

이진 탐색 알고리즘의 작동

가장 먼저 주목해야 할 것은 이진 검색 알고리즘 이 항상 정렬된 목록에서 작동한다는 것입니다. 따라서 첫 번째 논리적 단계는 제공된 목록을 정렬하는 것입니다. 정렬 후 목록의 중앙값을 원하는 값으로 확인합니다.

• 원하는 값이 중심 인덱스의 가치와 같으면 인덱스가 답변으로 반환됩니다.

• 목표 값이 중앙 인덱스의 목록 거래보다 낮으면 목록의 오른쪽이 무시됩니다.

• 원하는 값이 중앙 인덱스의 값보다 크면 왼쪽 절반이 버려집니다.

• 그런 다음 대상 값을 찾을 때까지 짧은 목록에서 프로세스가 반복됩니다.

예 #1

예제를 통해 알고리즘을 살펴보겠습니다. 다음 번호가 포함된 목록이 있다고 가정합니다.

1, 15, 23, 7, 6, 14, 8, 3, 27

원하는 값을 27로 가정하겠습니다. 목록의 총 요소 수는 9입니다.

첫 번째 단계는 목록을 정렬하는 것입니다. 정렬 후 목록은 다음과 같습니다.

1, 3, 6, 7, 8, 14, 15, 23, 27

목록의 요소 수가 9이므로 중심 인덱스는 5가 됩니다. 인덱스 5의 값은 8입니다. 원하는 값 27과 값 8을 비교합니다. 먼저 값이 8인지 확인합니다. 그렇다면 인덱스를 반환하고 종료합니다.

27은 8보다 크므로 왼쪽 부분을 무시하고 목록의 오른쪽만 탐색합니다. 순회할 새 목록은 다음과 같습니다.

14, 15, 23, 27

참고: 실제로 목록은 잘리지 않습니다. 관찰 범위만 좁혀집니다. 따라서 "새 목록"을 새 목록을 만들거나 원래 목록을 줄이는 것과 혼동해서는 안 됩니다. 새 목록으로 구현할 수 있지만 두 가지 문제가 있습니다. 먼저 메모리 오버헤드가 발생합니다. 각각의 새 목록은 공간 복잡성을 증가시킵니다. 둘째, 각 반복에서 원래 인덱스를 추적해야 합니다.

새로운 중앙 인덱스는 구현에 따라 두 번째 또는 세 번째 요소로 사용할 수 있습니다. 여기서 우리는 세 번째 요소를 중심으로 고려할 것입니다. 값 23은 값 27과 비교됩니다. 값이 중앙 값보다 크면 왼쪽 절반을 버립니다.

순회할 목록은 다음과 같습니다.

27

목록에는 단일 요소만 포함되어 있으므로 중심 요소로 간주됩니다. 따라서 원하는 값을 27과 비교합니다. 일치하면 원래 목록에서 인덱스 값 27을 반환합니다.

예 #2

같은 목록에서 원하는 값을 2로 가정해 보겠습니다.

먼저 중심 값 8을 2와 비교합니다. 원하는 값이 중심 값보다 작기 때문에 초점을 목록의 왼쪽으로 좁힙니다.

새 순회는 다음으로 구성됩니다.

1, 3, 6, 7

중심 요소를 두 번째 요소로 사용합시다. 원하는 값 2는 3과 비교됩니다. 값이 여전히 작기 때문에 포커스를 다시 목록의 왼쪽으로 좁힙니다.

새 순회는 다음으로 구성됩니다.

1

순회 목록에는 하나의 요소만 있으므로 값은 나머지 요소와 직접 비교됩니다. 값이 일치하지 않음을 알 수 있습니다. 따라서 v alue not found 오류 메시지와 함께 루프에서 벗어 납니다.

데이터 과학 고급 인증, 250명 이상의 고용 파트너, 300시간 이상의 학습, 0% EMI

시간 및 공간 복잡성

이진 탐색 알고리즘 의 시간 복잡도 는 O(log n)입니다. 최상의 시간 복잡도는 중심 인덱스가 원하는 값과 직접 일치할 때 O(1)입니다. 최악의 시나리오는 목록의 맨 끝에 있는 값이나 목록에 없는 값일 수 있습니다.

이진 탐색 알고리즘 의 공간 복잡도는 알고리즘 구현에 따라 다릅니다. 이를 구현하는 두 가지 방법이 있습니다.

1. 반복 방법
2. 재귀적 방법

두 가지 방법은 구현에 두 가지 차이점이 있지만 매우 동일합니다. 첫째, 재귀 방법에는 루프가 없습니다. 둘째, 루프의 다음 반복에 새 값을 전달하는 대신 다음 재귀에 전달합니다. 반복 방법에서는 루프 조건을 통해 반복을 제어할 수 있지만 재귀 방법에서는 최대값과 최소값을 경계 조건으로 사용합니다.

반복 방법에서 공간 복잡도는 O(1)입니다. 재귀적 방법에서 공간 복잡도는 O(log n)입니다.

혜택

• 이진 검색 알고리즘 은 구현하기에 상당히 간단한 검색 알고리즘입니다 .

• 선형 검색에 비해 크게 개선되었으며 구현하기 어려운 검색 알고리즘과 비교하여 거의 동일한 성능을 보입니다.

• 이진 검색 알고리즘 은 목록을 순차적으로 결합하는 대신 모든 반복에서 목록을 반으로 나눕니다. 큰 목록에서 이 방법은 정말 유용할 수 있습니다.

체크아웃: 의사 결정 트리 분류: 알아야 할 모든 것

결론

이진 탐색 알고리즘 은 계산 영역에서 널리 사용되는 알고리즘입니다 . 크고 작은 데이터 세트 모두에서 잘 작동할 수 있는 뚱뚱하고 정확한 검색 알고리즘입니다. 이진 검색 알고리즘 은 구현하기에 간단하고 신뢰할 수 있는 알고리즘입니다 . 시간 및 공간 분석을 통해 이 특정 기술을 사용하는 이점이 분명합니다.

데이터 과학에 대해 자세히 알아보려면 IIIT-B & upGrad의 데이터 과학 PG 디플로마를 확인하세요. 이 PG 디플로마는 실무 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크숍, 업계 전문가와의 멘토링, 1- 업계 멘토와 일대일, 400시간 이상의 학습 및 최고의 기업과의 취업 지원.