선형 검색과 이진 검색: 선형 검색과 이진 검색의 차이점

소개

프로그래밍 언어의 연속 메모리 할당은 여러 데이터 포인트를 저장하는 유연한 구현을 제공합니다. 배열, 목록 등과 같은 인접한 데이터 구조에서 데이터를 분리하고 모든 유사한 데이터를 병합하려는 경우 이 기능을 최대한 활용할 수 있습니다.

연속 메모리 할당은 컴퓨터의 운영 체제, 데이터베이스 관리 시스템 등과 같은 실제 응용 프로그램에서 많이 구현됩니다. 이 데이터 구조는 어레이에 새 데이터 포인트를 추가하는 데 단일 시간 단위만 필요하기 때문에 유연한 것으로 간주됩니다. 오(1).

그러나 모든 실제 응용 프로그램이 데이터 액세스 명령에 의존하기 때문에 특정 항목을 보거나 특정 항목을 검색하려고 할 때 문제가 발생합니다. 그리고 이 작업은 프로세서와 메모리의 속도를 충족할 만큼 충분히 빨라야 합니다.

요소를 검색하기 위해 수행하는 비교 횟수에 따라 다양한 검색 알고리즘이 나뉩니다.

배열의 각 데이터 포인트를 비교하여 요소를 검색하면 순차 검색으로 간주됩니다. 그러나 일부 비교를 건너뛰어 몇 가지 요소만 비교하는 경우 간격 검색으로 간주됩니다. 그러나 간격 검색을 수행하려면 배열이 정렬된 순서(오름차순 또는 내림차순)가 필요합니다.

순차 탐색의 시간 복잡도는 선형 O(n)이고 이진 탐색(구간 탐색의 예)의 시간 복잡도는 O(log n)이다. 또한 지수 검색, 점프 검색 등과 같은 다른 검색 알고리즘이 있습니다.

그러나 선형 검색과 이진 검색이 주로 사용되며 선형 검색은 무작위 또는 정렬되지 않은 데이터에 대한 것이고 이진 검색은 정렬 및 정렬된 데이터에 대한 것입니다. 해싱은 데이터 포인트에 액세스하는 시간 복잡도가 O(1)인 특수 검색 알고리즘입니다.

먼저 선형 검색과 이진 검색의 알고리즘을 살펴보고 선형 검색과 이진 검색의 차이점을 비교하겠습니다.

선형 검색

이미 논의한 바와 같이 선형 검색 알고리즘은 배열의 각 요소를 비교하며, 이를 수행하는 코드는 다음과 같습니다.

코드를 살펴보겠습니다.

배열, 정수 키를 매개변수로 기대하는 linear_search 함수를 선언했습니다. 이제 모든 요소를 ​​반복하고 검색 키와 일치하는지 비교해야 하므로 배열을 반복하는 for 루프를 작성했으며 그 안에 해당 위치의 숫자가 일치하는지 확인하는 if 루프가 있습니다. 검색 키로 여부. 일치하는 항목을 찾으면 해당 위치를 반환합니다. 배열에 그러한 요소가 없으면 함수 끝에 -1을 반환합니다.

동일한 번호가 여러 번 나타나는 경우 첫 번째 발생 위치를 반환합니다.

main 메소드로 와서 정수 배열을 선언하고 초기화했습니다. 그런 다음 검색해야 하는 키를 초기화합니다. 여기서는 배열과 키를 하드코딩하지만 사용자 입력으로 변경할 수 있습니다. 이제 요소 목록과 검색할 키를 얻었으므로 선형 검색 메서드가 호출되고 반환된 인덱스가 기록됩니다. 나중에 반환된 값을 확인하고 키가 있으면 인덱스를 인쇄하고 그렇지 않으면 인쇄 키를 찾을 수 없습니다.

이진 검색

이진 검색은 선형 검색보다 최적화되어 있지만 이진 검색을 적용하려면 배열을 정렬해야 합니다. 그리고 이를 수행하는 코드가 있습니다.

코드를 살펴보겠습니다.

정렬된 정수 배열과 정수 키를 매개변수로 기대하는 binary_search 메서드를 선언했습니다. 우리는 변수를 low, high, mid를 초기화하고 있습니다. 여기서 low, high는 low가 0 인덱스에 있고 high가 처음에 n 인덱스에 있는 포인터입니다. 이진 검색은 어떻게 작동합니까?

처음에는 낮음과 높음의 중간을 계산합니다. 중간을 (낮음+높음)/2로 계산할 수 있지만 때로는 높음이 큰 숫자가 될 수 있으며 높음에 낮음을 더하면 정수 오버플로가 발생할 수 있습니다. 따라서 mid를 low+(high-low)/2로 계산하는 것이 최적의 방법이 될 것입니다.

중간에 있는 요소를 검색 키와 비교하고 일치하는 항목을 찾으면 인덱스를 반환합니다. 그렇지 않으면 중간 요소가 키보다 크거나 키보다 작은지 확인합니다. mid가 더 크면 배열의 후반부에 있는 모든 요소가 키보다 크기 때문에 배열의 전반부만 확인해야 하므로 high를 mid-1로 업데이트합니다.

유사하게 mid가 키보다 작으면 배열의 후반부에서 검색해야 하므로 low를 mid+1로 업데이트해야 합니다. 각 반복에서 배열의 절반 중 하나를 무시하기 때문에 이진 검색은 감소 및 정복 알고리즘을 기반으로 함을 기억하십시오.

코드로 돌아가서 main 메서드를 구축했습니다. 정렬된 배열과 검색 키를 초기화하고 이진 검색을 호출하고 결과를 인쇄했습니다.

이제 선형 검색과 이진 검색의 알고리즘을 살펴보았으므로 두 알고리즘을 모두 비교해 보겠습니다.

선형 검색 대 이진 검색

일하고있는

• 선형 검색은 모든 요소를 ​​반복하고 검색해야 하는 키와 비교합니다.
• 이진 검색은 검색해야 하는 배열의 크기를 현명하게 줄이고 매번 키와 중간 요소를 비교합니다.

데이터 구조

• 선형 검색은 배열, 목록, 연결 목록 등과 같은 모든 데이터 구조에서 유연합니다.
• 다방향 탐색이 필요하기 때문에 모든 데이터 구조에 대해 이진 검색을 수행할 수 없습니다. 따라서 단일 연결 목록과 같은 데이터 구조는 사용할 수 없습니다.

전제 조건

• 선형 검색은 모든 유형의 데이터에 대해 수행할 수 있으며 데이터는 무작위로 정렬되거나 알고리즘이 동일하게 유지될 수 있습니다. 따라서 사전 작업을 수행할 필요가 없습니다.
• 이진 검색은 정렬된 배열에서만 작동합니다. 따라서 배열 정렬은 이 알고리즘의 전제 조건입니다.

사용 사례

• 선형 검색은 일반적으로 더 작고 무작위로 정렬된 데이터 세트에 선호됩니다.
• 이진 검색은 비교적 크고 정렬된 데이터 세트에 대해 선호됩니다.

유효성

• 선형 검색은 더 큰 데이터 세트의 경우 덜 효율적입니다.
• 이진 검색은 더 큰 데이터 세트의 경우 더 효율적입니다.

시간 복잡도

• 선형 검색에서 가장 좋은 경우 복잡도는 요소가 첫 번째 인덱스에서 발견되는 O(1)입니다. 최악의 경우 복잡성은 요소가 마지막 인덱스에서 발견되거나 요소가 배열에 없는 경우 O(n)입니다.
• 이진 검색에서 가장 좋은 경우 복잡도는 요소가 중간 인덱스에서 발견되는 O(1)입니다. 최악의 복잡도는 O( log 2 n)입니다.

드라이 런

크기가 10,000인 배열이 있다고 가정해 보겠습니다.

• 선형 탐색에서 최상의 복잡도는 O(1)이고 최악의 복잡도는 O(10000)입니다.
• 이진 검색에서 최상의 복잡도는 O(1)이고 최악의 복잡도는 O( log 2 10000)=O(13.287)입니다.

결론

우리는 배열에서 데이터 액세스의 중요성을 이해하고 선형 검색 및 이진 검색의 알고리즘을 이해했습니다. 선형 검색 및 이진 검색의 코드를 살펴보았습니다. 선형 검색과 이진 검색의 차이점을 비교하여 대규모 예제를 테스트했습니다.

이제 선형 검색과 이진 검색의 차이점을 알았으므로 대규모 데이터 세트에 대해 두 코드를 모두 실행하고 실행 시간을 비교하고 다양한 검색 알고리즘을 탐색하고 구현해 보십시오!

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

세계 최고의 대학에서 온라인으로 데이터 과학 과정 을 배우십시오 . 이그 제 큐 티브 PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 획득하여 경력을 빠르게 추적하십시오.