이진 검색

이진 검색은 가장 인기 있고 효율적인 검색 알고리즘입니다. 실제로 가장 빠른 검색 알고리즘입니다. 점프 정렬과 마찬가지로 정렬 할 배열도 필요합니다. 배열을 두 부분으로 나눈 다음 검색중인 항목을 중간 항목과 비교하는 분할 및 정복 접근 방식을 기반으로합니다. 중간 항목이 일치하면 중간 요소의 인덱스를 반환합니다. 그렇지 않으면 항목의 값에 따라 왼쪽과 오른쪽으로 이동합니다.

이진 검색 알고리즘

n요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정하고X요소를 찾으려고합니다.

이진 검색 예

배열 :(1, 2, 3, 4, 5, 6, 7, 8, 9)가 있고 X-8을 찾고 싶다고 가정합니다.

이진 검색 알고리즘 구현

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 8;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

이진 검색 알고리즘 복잡성

시간 복잡성

• 평균 사례

이진 검색을 수행 할 때 절반을 검색하고 나머지 절반을 버려 매번 배열 크기를 절반으로 줄입니다.

시간 복잡도에 대한 표현은 반복에 의해 주어집니다.

T(n) = T(n/2) + k , k is a constant.

이 반복의 결과는logn을 제공하며 시간 복잡도는O(logn)순서입니다. 선형 검색 및 점프 검색보다 빠릅니다.

• 베스트 케이스

가장 좋은 경우는 중간 요소가 검색중인 요소이고 첫 번째 반복에서 반환 될 때 발생합니다. 최상의 경우 시간 복잡도는O(1)입니다.

• 최악의 경우

최악의 시간 복잡성은 평균 시간 복잡성과 동일합니다. 최악의 시간 복잡도는O(logn)입니다.

공간 복잡성

이 알고리즘의 공간 복잡성은 임시 변수 이외의 데이터 구조가 필요하지 않기 때문에 반복 구현의 경우O(1)입니다.

재귀 구현의 경우 재귀 호출 스택에 필요한 공간으로 인해 공간 복잡도가O(logn)입니다.