logo

TechCodeview

이진 검색 알고리즘 – 반복 및 재귀 구현

이진 검색 연산 는 검색 알고리즘 정렬된 배열에 사용됨 반복적으로 검색 간격을 반으로 나누기 . 이진 검색의 아이디어는 배열이 정렬된 정보를 사용하여 시간 복잡도를 O(log N)로 줄이는 것입니다.

바이너리 검색 내에서 목표 값의 위치를 ​​찾는 데 사용되는 검색 알고리즘입니다. 정렬됨 정렬. 목표 값을 찾거나 간격이 비어 있을 때까지 검색 간격을 반으로 반복적으로 나누는 방식으로 작동합니다. 대상 요소와 검색 공간의 중간 값을 비교하여 검색 간격을 절반으로 줄입니다.

마이스페이스가 뭐야?

이진 검색 알고리즘을 적용하려면:



  • 데이터 구조를 정렬해야 합니다.
  • 데이터 구조의 모든 요소에 액세스하려면 일정한 시간이 걸립니다.

이진 검색 알고리즘:

이 알고리즘에서는

  • 검색 공간을 다음과 같이 두 부분으로 나눕니다. 중간 인덱스 mid 찾기 .

이진 검색 알고리즘에서 중간 인덱스 mid 찾기

  • 검색 공간의 중간 요소를 키와 비교합니다.
  • 중간 요소에서 키를 찾으면 프로세스가 종료됩니다.
  • 중간 요소에서 키를 찾을 수 없는 경우 다음 검색 공간으로 사용할 절반을 선택합니다.
    • 키가 중간 요소보다 작으면 다음 검색에 왼쪽이 사용됩니다.
    • 키가 중간 요소보다 크면 다음 검색에 오른쪽이 사용됩니다.
  • 이 프로세스는 키를 찾거나 전체 검색 공간이 소진될 때까지 계속됩니다.

이진 검색 알고리즘은 어떻게 작동하나요?

이진 검색의 작동을 이해하려면 다음 그림을 고려하십시오.

배열을 고려해보세요 arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} , 그리고 목표 = 23 .

첫 번째 단계: mid를 계산하고 mid 요소를 키와 비교합니다. 키가 중간 요소보다 작으면 왼쪽으로 이동하고, 중간보다 크면 검색 공간을 오른쪽으로 이동합니다.

  • 키(예: 23)는 현재 중간 요소(예: 16)보다 큽니다. 검색 공간이 오른쪽으로 이동합니다.

이진 검색 알고리즘 : 키를 16과 비교

  • 키는 현재 56중반보다 작습니다. 검색공간이 왼쪽으로 이동합니다.

이진 검색 알고리즘 : 키를 56과 비교

두번째 단계: 키가 mid 요소의 값과 일치하면 요소가 발견되고 검색이 중지됩니다.

이진 검색 알고리즘 : mid와 주요 일치

권장 연습 이진 검색 사용해 보세요!

그만큼 이진 검색 알고리즘 다음 두 가지 방법으로 구현할 수 있습니다

  • 반복 이진 검색 알고리즘
  • 재귀 이진 검색 알고리즘

아래에는 접근 방식에 대한 의사코드가 나와 있습니다.

반복 이진 검색 알고리즘:

여기서는 while 루프를 사용하여 키를 비교하고 검색 공간을 두 부분으로 분할하는 프로세스를 계속합니다.

반복적 이진 검색 알고리즘 구현:

C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
씨 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
자바 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
파이썬 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
씨# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
자바스크립트 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= 낮음) { 중간 = 낮음 + Math.floor((높음 - 낮음) / 2);    // 요소가 중앙에 있는 경우 // 그 자체입니다. if (arr[mid] == x) return mid;    // 요소가 mid보다 작으면 // (arr[mid]> x) high = mid - 1인 경우에만 왼쪽 하위 배열에만 존재할 수 있습니다.    // 그렇지 않으면 요소는 // 오른쪽 하위 배열에만 존재할 수 있습니다. else low = mid + 1;  } // 요소가 배열에 없으면 // 여기에 도달합니다. return -1; } arr =new 배열(2, 3, 4, 10, 40);  x = 10;  n = 배열 ​​길이;  결과 = 바이너리 검색(arr, x);   (결과 == -1) ? console.log('배열에 요소가 없습니다') : console.log('인덱스에 요소가 있습니다' + result);   // 이 코드는 simranarora5sos 및 rshuklabbb에 의해 제공되었습니다.>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>
산출 
Element is present at index 3>

시간 복잡도: 오(로그 N)
보조 공간: 오(1)

재귀 이진 검색 알고리즘:

재귀 함수를 만들고 검색 공간의 중간 부분을 키와 비교합니다. 그리고 결과에 따라 키가 발견된 인덱스를 반환하거나 다음 검색 공간에 대한 재귀 함수를 호출합니다.

재귀 이진 검색 알고리즘 구현:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= 낮음) { int mid = 낮음 + (높음 - 낮음) / 2;  // 요소가 중간에 존재하는 경우 // 그 자체입니다. if (arr[mid] == x) return mid;  // 요소가 mid보다 작으면 // 왼쪽 하위 배열에만 존재할 수 있습니다. if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // 그렇지 않으면 요소는 // 오른쪽 하위 배열에만 존재할 수 있습니다. return binarySearch(arr, mid + 1, high, x);  } } // 드라이버 코드 int main() { int arr[] = { 2, 3, 4, 10, 40 };  int 쿼리 = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, query);  (결과 == -1) ? 시합<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
씨 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= 낮음) { int mid = 낮음 + (높음 - 낮음) / 2;  // 요소가 중간에 존재하는 경우 // 그 자체입니다. if (arr[mid] == x) return mid;  // 요소가 mid보다 작으면 // 왼쪽 하위 배열에만 존재할 수 있습니다. if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // 그렇지 않으면 요소는 // 오른쪽 하위 배열에만 존재할 수 있습니다. return binarySearch(arr, mid + 1, high, x);  } // 요소가 배열에 없으면 // 여기에 도달합니다. return -1; } // 드라이버 코드 int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  정수 x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (결과 == -1) ? printf('요소가 배열에 존재하지 않습니다') : printf('요소가 인덱스 %d에 존재합니다', result);  0을 반환합니다. }>
자바 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= 낮음) { int mid = 낮음 + (높음 - 낮음) / 2;  // 요소가 중간 자체에 존재하는 경우 // if (arr[mid] == x) return mid;  // 요소가 mid보다 작으면 // 왼쪽 하위 배열에만 존재할 수 있습니다. if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // 그렇지 않으면 요소는 // 오른쪽 하위 배열에만 존재할 수 있습니다. return binarySearch(arr, mid + 1, high, x);  } // 배열에 요소가 없으면 여기에 도달합니다. // return -1;  } // 드라이버 코드 public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  정수 x = 10;  int result = ob.binarySearch(arr, 0, n - 1, x);  if (결과 == -1) System.out.println( '배열에 요소가 없습니다');  else System.out.println( '요소가 인덱스에 존재합니다 ' + result);  } } /* 이 코드는 Rajat Mishra가 제공한 것입니다 */>
파이썬 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= low: mid = low + (high - low) // 2 # 요소가 중앙 자체에 존재하는 경우 if arr[mid] == x: return mid # 요소가 mid보다 작으면 # 존재할 수만 있습니다. 왼쪽 하위 배열 elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # 그렇지 않으면 요소는 # 오른쪽 하위 배열에만 존재할 수 있습니다. else: return binarySearch(arr, mid + 1, high, x ) # 요소가 배열에 존재하지 않습니다. else: return -1 # 드라이버 코드 if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # 함수 호출 결과 = binarySearch( arr, 0, len(arr)-1, x) if result != -1: print('요소가 인덱스에 있습니다', result) else: print('요소가 배열에 없습니다')>
씨# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= 낮음) { int mid = 낮음 + (높음 - 낮음) / 2;  // 요소가 중간 자체에 존재하는 경우 // if (arr[mid] == x) return mid;  // 요소가 mid보다 작으면 // 왼쪽 하위 배열에만 존재할 수 있습니다. if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // 그렇지 않으면 요소는 // 오른쪽 하위 배열에만 존재할 수 있습니다. return binarySearch(arr, mid + 1, high, x);  } // 배열에 요소가 없으면 여기에 도달합니다. // return -1;  } // 드라이버 코드 public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.길이;  정수 x = 10;  int result = binarySearch(arr, 0, n - 1, x);  if (결과 == -1) Console.WriteLine( '요소가 arrau에 없습니다');  else Console.WriteLine('요소는 인덱스에 존재합니다 ' + 결과);  } } // 이 코드는 Sam007이 제공한 것입니다.>
자바스크립트 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= 낮음) { mid = 낮음 + Math.floor((높음 - 낮음) / 2);  // 요소가 중간에 존재하는 경우 // 그 자체입니다. if (arr[mid] == x) return mid;  // 요소가 mid보다 작으면 // 왼쪽 하위 배열에만 존재할 수 있습니다. if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // 그렇지 않으면 요소는 // 오른쪽 하위 배열에만 존재할 수 있습니다. return binarySearch(arr, mid + 1, high, x);  } // 요소가 배열에 없으면 // 여기에 도달합니다. return -1; } arr = [ 2, 3, 4, 10, 40 ]; x = 10이라고 하자; let n = arr.length let result = binarySearch(arr, 0, n - 1, x); (결과 == -1) ? console.log( '배열에 요소가 없습니다') : console.log('인덱스에 요소가 있습니다 ' +result);>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $low) { $mid = ceil($low + ($high - $low) / 2); // 요소가 존재하는 경우 // 중간 자체에 if ($arr[$mid] == $x) return Floor($mid); // 요소가 mid보다 작으면 // 왼쪽 하위 배열에만 존재할 수 있습니다. if ($arr[$mid]> $x) return binarySearch($arr, $low, $mid - 1, $x ); // 그렇지 않으면 요소는 // 오른쪽 하위 배열에만 존재할 수 있습니다. return binarySearch($arr, $mid + 1, $high, $x); } // 요소가 배열에 없으면 // 여기에 도달합니다. return -1; } // 드라이버 코드 $arr = array(2, 3, 4, 10, 40); $n = 개수($arr); $x = 10; $result = 바이너리 검색($arr, 0, $n - 1, $x); if(($result == -1)) echo '배열에 요소가 없습니다'; else echo '요소가 인덱스에 존재합니다 ', $result; ?>>
산출 
Element is present at index 3>
  • 시간 복잡도:
    • 최선의 경우: O(1)
    • 평균 사례: O(log N)
    • 최악의 경우: O(log N)
  • 보조 공간: O(1), 재귀 호출 스택을 고려하면 보조 공간은 O(logN)이 됩니다.
  • 이진 검색은 신경망 훈련 알고리즘이나 모델에 대한 최적의 하이퍼파라미터 찾기 등 기계 학습에 사용되는 보다 복잡한 알고리즘을 위한 빌딩 블록으로 사용될 수 있습니다.
  • 광선 추적이나 텍스처 매핑을 위한 알고리즘과 같은 컴퓨터 그래픽에서 검색하는 데 사용할 수 있습니다.
  • 데이터베이스를 검색하는 데 사용할 수 있습니다.
  • 이진 검색은 특히 대규모 배열의 경우 선형 검색보다 빠릅니다.
  • 보간 검색이나 지수 검색과 같이 시간 복잡도가 유사한 다른 검색 알고리즘보다 더 효율적입니다.
  • 이진 검색은 하드 드라이브나 클라우드와 같은 외부 메모리에 저장된 대규모 데이터 세트를 검색하는 데 매우 적합합니다.
  • 배열이 정렬되어야 합니다.
  • 이진 검색을 위해서는 검색 중인 데이터 구조가 연속적인 메모리 위치에 저장되어 있어야 합니다.
  • 이진 검색에서는 배열 요소가 비교 가능해야 합니다. 즉, 순서를 지정할 수 있어야 합니다.

바이너리 검색에 대한 자주 묻는 질문(FAQ):

1. 이진 검색이란 무엇입니까?

이진 검색은 정렬된 배열 내에서 목표 값을 찾는 효율적인 알고리즘입니다. 검색 간격을 반복적으로 절반으로 나누어 작동합니다.

2. 바이너리 검색은 어떻게 작동하나요?

이진 검색은 대상 값을 배열의 중간 요소와 비교합니다. 동일하면 검색이 성공한 것입니다. 대상이 중간 요소보다 작으면 배열의 아래쪽 절반에서 검색이 계속됩니다. 대상이 더 크면 위쪽 절반에서 검색이 계속됩니다. 이 프로세스는 대상을 찾거나 검색 간격이 비어 있을 때까지 반복됩니다.

3. 이진 검색의 시간 복잡도는 얼마입니까?

이진 탐색의 시간복잡도는 O(log2n), 여기서 n은 배열의 요소 수입니다. 이는 각 단계에서 검색 간격의 크기가 절반으로 줄어들기 때문입니다.

4. 이진 검색의 전제 조건은 무엇입니까?

이진 검색에서는 배열이 오름차순 또는 내림차순으로 정렬되어야 합니다. 배열이 정렬되어 있지 않으면 이진 검색을 사용하여 배열의 요소를 검색할 수 없습니다.

5. 이진 검색을 위해 배열이 정렬되지 않으면 어떻게 되나요?

배열이 정렬되지 않은 경우 이진 검색이 잘못된 결과를 반환할 수 있습니다. 배열의 정렬된 특성에 따라 검색할 배열의 절반을 결정합니다.

6. 숫자가 아닌 데이터에도 이진 검색을 적용할 수 있나요?

예, 요소에 대해 정의된 순서가 있는 한 숫자가 아닌 데이터에 이진 검색을 적용할 수 있습니다. 예를 들어 문자열을 알파벳순으로 검색하는 데 사용할 수 있습니다.

7. 이진 검색의 일반적인 단점은 무엇입니까?

이진 검색의 단점은 대상 요소의 어느 부분이 놓일 수 있는지 결정하기 위해 입력 배열을 정렬해야 한다는 것입니다. 따라서 정렬되지 않은 배열의 경우 이진 검색을 적용하기 전에 배열을 정렬해야 합니다.

8. 이진 검색은 언제 사용해야 합니까?

정렬된 배열에서 대상 값을 검색할 때, 특히 배열의 크기가 큰 경우 이진 검색을 사용해야 합니다. 선형 검색 알고리즘에 비해 대규모 데이터 세트에 특히 효율적입니다.

9. 이진 검색을 재귀적으로 구현할 수 있나요?

예, 이진 검색은 반복적으로나 재귀적으로 구현할 수 있습니다. 재귀 구현은 종종 더 간결한 코드로 이어지지만 재귀 스택 공간이나 함수 호출로 인해 오버헤드가 약간 더 높을 수 있습니다.

10. 이진 검색은 정렬된 배열 검색에 항상 최선의 선택입니까?

이진 검색은 정렬된 배열을 검색하는 데 매우 효율적이지만 작은 데이터 세트를 처리하거나 배열이 자주 수정되는 경우와 같이 다른 검색 알고리즘이 더 적합한 특정 경우가 있을 수 있습니다.

문자열을 정수로 변환

관련 기사:

  • 문제가 있는 답변 튜토리얼의 이진 검색
  • 선형 검색과 이진 검색
  • 이진 검색 문제를 식별하고 해결하는 방법은 무엇입니까?