선형 검색과 이진 검색의 주요 차이점은 이진 검색은 정렬 된 요소 목록에서 요소를 검색하는 데 걸리는 시간이 짧습니다. 따라서 이진 탐색 방법의 효율성은 선형 탐색보다 더 크다고 추론된다.
둘 사이의 또 다른 차이점은 이진 검색을위한 전제 조건이 있다는 것입니다. 즉, 선형 검색에서 엘리먼트를 정렬 해야하며 그러한 전제 조건은 없습니다. 두 검색 방법 모두 아래에서 설명하는 다른 기술을 사용하지만.
비교 차트
| 비교 근거 | 선형 검색 | 이진 검색 |
|---|---|---|
| 시간 복잡성 | 에) | O (log 2 N) |
| 최우수 사례 시간 | 첫 번째 요소 O (1) | 중심 요소 O (1) |
| 배열의 전제 조건 | 필요 없음 | 배열은 정렬 된 순서 여야합니다. |
| N 개의 요소에 대한 최악의 경우 | N 개의 비교가 필요합니다. | 로그 2 N 비교 후에 만 결론을 내릴 수 있음 |
| 에 구현할 수 있습니다. | 배열 및 링크 된 목록 | 연결된 목록에 직접 구현할 수 없습니다. |
| 삽입 작업 | 목록의 끝에 쉽게 삽입됩니다. | 정렬 된 목록을 유지하기 위해 적절한 위치에 삽입하는 처리가 필요합니다. |
| 알고리즘 유형 | 반복적 인 성질 | 자연에서 나누고 정복하십시오. |
| 유용성 | 사용하기 쉽고 주문한 요소가 필요 없습니다. | 아무 래도 까다로운 알고리즘 및 요소를 순서대로 구성해야합니다. |
| 코드 라인 | 적게 | 더 |
선형 검색의 정의
선형 검색에서 배열의 각 요소는 하나씩 논리적 순서로 검색되어 원하는 요소인지 여부를 확인합니다. 모든 요소에 액세스하고 원하는 요소를 찾을 수없는 경우 검색에 실패합니다. 최악의 경우, 어레이의 크기 (n / 2)의 절반을 스캔해야하는 평균적인 경우의 수입니다.
따라서 선형 검색은 배열을 순차적으로 탐색하여 주어진 항목을 찾는 기법으로 정의 할 수 있습니다. 아래 주어진 프로그램은 검색을 사용하여 배열 요소를 검색하는 방법을 보여줍니다.
선형 검색의 효율성
검색 테이블에서 레코드를 검색 할 때 수행 한 시간 소비 또는 비교 횟수는 기술의 효율성을 결정합니다. 원하는 레코드가 검색 테이블의 첫 번째 위치에 있으면 하나의 비교 만 수행됩니다. 원하는 레코드가 마지막 레코드 인 경우 n 개의 비교를 수행해야합니다. 레코드가 검색 테이블의 어딘가에 나타나면 평균으로 비교 수가 (n + 1 / 2)가됩니다. 이 기법의 최악의 경우 효율성은 O (n)이 실행 순서를 나타냅니다.
C 선형 탐색 기술로 요소를 탐색하는 프로그램 .
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ( "\ n 요소 수 입력 :"); scanf ( "% d", & n); printf ( "숫자 입력 : \ n"); (i = 0; i = n-1; i ++) {scanf ( "% d", & a [i]); } printf ( "\ n 검색 할 번호를 입력하십시오 :"); scanf ( "% d", & item); for (i = 0; i = 0) {printf ( "\ n % d은 % d 위치에 있습니다 :", item, loc + 1); } else {printf ( "\ n 항목이 존재하지 않습니다"); } getch (); } 이진 검색의 정의
이진 검색은 매우 효율적인 알고리즘입니다. 이 검색 기술은 가능한 최소의 비교에서 주어진 항목을 검색하는데 더 적은 시간을 소비합니다. 이진 검색을 수행하려면 먼저 배열 요소를 정렬해야합니다.
이 기법의 논리는 다음과 같습니다.
- 먼저 배열의 가운데 요소를 찾습니다.
- 배열의 중간 요소는 검색 될 요소와 비교됩니다.
세 가지 경우가 발생할 수 있습니다.
- 요소가 필수 요소이면 검색에 성공한 것입니다.
- 요소가 원하는 항목보다 작 으면 배열의 첫 번째 절반 만 검색하십시오.
- 원하는 요소보다 큰 경우 배열의 두 번째 절반에서 검색하십시오.
요소가 발견되거나 탐색 영역에서 배기 될 때까지 동일한 단계를 반복하십시오. 이 알고리즘에서는 매번 검색 영역이 축소됩니다. 따라서 비교 횟수는 log (N + 1) 이하 여야합니다. 따라서 선형 검색과 비교할 때 효율적인 알고리즘이지만 이진 검색을 수행하기 전에 배열을 정렬해야합니다.
C 바이너리 검색 기술로 요소를 찾는 프로그램 .
#include void main () {int i, beg, end, middle, n, search, array [100]; printf ( "요소의 수를 입력하십시오 \ n"); scanf ( "% d", & n); printf ( "% d 숫자를 입력하십시오 \ n", n); for (i = 0; i <n; i ++) scanf ( "% d", & array [i]); printf ( "검색 할 번호 입력 \ n"); scanf ( "% d", & search); beg = 0; end = n-1; 중간 = (beg + end) / 2; while (beg <= end) {if (array [middle] end) printf ( "검색에 실패했습니다! % d이 목록에 없습니다. \ n", 검색); getch (); } 선형 검색과 이진 검색의 주요 차이점
- 선형 검색은 본질적으로 반복적이며 순차적 접근 방식을 사용합니다. 반면에 바이너리 검색은 분할 및 정복 접근 방식을 구현합니다.
- 선형 탐색의 시간 복잡도는 O (N)이고 이진 탐색은 O (log 2 N)이다.
- 선형 탐색에서 가장 좋은 경우는 첫 번째 요소 즉, O (1)입니다. 반대로, 이진 검색에서 중간 요소, 즉 O (1)에 대한 것입니다.
- 선형 검색에서 요소를 검색하는 최악의 경우는 N 개의 비교입니다. 대조적으로, 이진 검색에 대한 로그 2 N 비교 수입니다.
- 선형 검색은 링크 목록뿐만 아니라 배열에서도 구현할 수 있지만 이진 검색은 연결된 목록에서 직접 구현할 수 없습니다.
- 우리가 알고 있듯이 바이너리 검색은 정렬 된 배열을 필요로합니다. 정렬 된 목록을 유지하기 위해 적절한 위치에 삽입하는 처리가 필요합니다. 반대로 선형 검색에는 정렬 된 요소가 필요 없기 때문에 요소가 목록 끝에 쉽게 삽입됩니다.
- 선형 검색은 사용하기 쉽고 순서가 지정된 요소가 필요하지 않습니다. 반면, 이진 검색 알고리즘은 까다 롭고 요소가 반드시 순서대로 정렬됩니다.
결론
선형 및 이진 검색 알고리즘은 응용 프로그램에 따라 유용 할 수 있습니다. 배열이 데이터 구조이고 요소가 정렬 된 순서로 정렬되면 빠른 검색을 위해 이진 검색이 좋습니다. 링크 된리스트가 요소 정렬 방식에 관계없이 데이터 구조 인 경우 이진 검색 알고리즘을 직접 구현할 수 없기 때문에 선형 검색이 채택됩니다.
링크리스트는 본질적으로 동적이고 중간 요소가 실제로 할당 된 위치를 알 수 없기 때문에 일반적인 Binary 검색 알고리즘을 링크 된 목록에 사용할 수 없습니다. 따라서 이진 검색은 선형 검색보다 실행이 빠르기 때문에 연결된 목록에서도 작동 할 수있는 이진 검색 알고리즘의 변형을 설계해야합니다.
