추천, 2024

에디터의 선택

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

선형 검색 및 이진 검색은 요소 검색을 위해 배열에서 사용되는 두 가지 방법입니다. 검색은 임의의 순서 또는 무작위로 저장된 요소 목록 내의 요소를 찾는 프로세스입니다.

선형 검색과 이진 검색의 주요 차이점은 이진 검색은 정렬 된 요소 목록에서 요소를 검색하는 데 걸리는 시간이 짧습니다. 따라서 이진 탐색 방법의 효율성은 선형 탐색보다 더 크다고 추론된다.

둘 사이의 또 다른 차이점은 이진 검색을위한 전제 조건이 있다는 것입니다. 즉, 선형 검색에서 엘리먼트를 정렬 해야하며 그러한 전제 조건은 없습니다. 두 검색 방법 모두 아래에서 설명하는 다른 기술을 사용하지만.

비교 차트

비교 근거선형 검색이진 검색
시간 복잡성에)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 (); } 

이진 검색의 정의

이진 검색은 매우 효율적인 알고리즘입니다. 이 검색 기술은 가능한 최소의 비교에서 주어진 항목을 검색하는데 더 적은 시간을 소비합니다. 이진 검색을 수행하려면 먼저 배열 요소를 정렬해야합니다.

이 기법의 논리는 다음과 같습니다.

  • 먼저 배열의 가운데 요소를 찾습니다.
  • 배열의 중간 요소는 검색 될 요소와 비교됩니다.

세 가지 경우가 발생할 수 있습니다.

  1. 요소가 필수 요소이면 검색에 성공한 것입니다.
  2. 요소가 원하는 항목보다 작 으면 배열의 첫 번째 절반 만 검색하십시오.
  3. 원하는 요소보다 큰 경우 배열의 두 번째 절반에서 검색하십시오.

요소가 발견되거나 탐색 영역에서 배기 될 때까지 동일한 단계를 반복하십시오. 이 알고리즘에서는 매번 검색 영역이 축소됩니다. 따라서 비교 횟수는 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 (); } 

선형 검색과 이진 검색의 주요 차이점

  1. 선형 검색은 본질적으로 반복적이며 순차적 접근 방식을 사용합니다. 반면에 바이너리 검색은 분할 및 정복 접근 방식을 구현합니다.
  2. 선형 탐색의 시간 복잡도는 O (N)이고 이진 탐색은 O (log 2 N)이다.
  3. 선형 탐색에서 가장 좋은 경우는 첫 번째 요소 즉, O (1)입니다. 반대로, 이진 검색에서 중간 요소, 즉 O (1)에 대한 것입니다.
  4. 선형 검색에서 요소를 검색하는 최악의 경우는 N 개의 비교입니다. 대조적으로, 이진 검색에 대한 로그 2 N 비교 수입니다.
  5. 선형 검색은 링크 목록뿐만 아니라 배열에서도 구현할 수 있지만 이진 검색은 연결된 목록에서 직접 구현할 수 없습니다.
  6. 우리가 알고 있듯이 바이너리 검색은 정렬 된 배열을 필요로합니다. 정렬 된 목록을 유지하기 위해 적절한 위치에 삽입하는 처리가 필요합니다. 반대로 선형 검색에는 정렬 된 요소가 필요 없기 때문에 요소가 목록 끝에 쉽게 삽입됩니다.
  7. 선형 검색은 사용하기 쉽고 순서가 지정된 요소가 필요하지 않습니다. 반면, 이진 검색 알고리즘은 까다 롭고 요소가 반드시 순서대로 정렬됩니다.

결론

선형 및 이진 검색 알고리즘은 응용 프로그램에 따라 유용 할 수 있습니다. 배열이 데이터 구조이고 요소가 정렬 된 순서로 정렬되면 빠른 검색을 위해 이진 검색이 좋습니다. 링크 된리스트가 요소 정렬 방식에 관계없이 데이터 구조 인 경우 이진 검색 알고리즘을 직접 구현할 수 없기 때문에 선형 검색이 채택됩니다.

링크리스트는 본질적으로 동적이고 중간 요소가 실제로 할당 된 위치를 알 수 없기 때문에 일반적인 Binary 검색 알고리즘을 링크 된 목록에 사용할 수 없습니다. 따라서 이진 검색은 선형 검색보다 실행이 빠르기 때문에 연결된 목록에서도 작동 할 수있는 이진 검색 알고리즘의 변형을 설계해야합니다.

Top