C의 이진 검색 알고리즘

정렬된 배열에서 특정 요소를 찾는 빠른 방법은 이진 검색입니다. 이 알고리즘의 초기 작업은 목표 값을 배열의 중간 요소와 비교하는 것입니다. 중간 요소에 대상 값이 포함되면 검색이 성공한 것으로 간주됩니다. 목표 값이 중앙 요소보다 작은 경우 알고리즘은 배열의 왼쪽 절반을 찾습니다. 목표 값이 중앙 요소보다 큰 경우 프로그램은 배열의 오른쪽 절반을 스캔합니다. 이 방법은 목표값 또는 검색 범위가 소진될 때까지 반복됩니다.

용법:

데이터베이스, 검색 엔진 및 데이터 처리는 이진 검색 전략을 사용하는 응용 프로그램 중 일부에 불과합니다.

형질:

입력 값의 배열을 정렬해야 합니다.
반복할 때마다 이 방법은 검색 범위를 절반으로 줄여 대규모 데이터 세트에 특히 효율적입니다.
알고리즘은 최악의 경우 O(log n) 시간 복잡도를 갖습니다.
원하는 값을 찾는 것은 프로그램에서 분할 정복 전략을 사용하여 수행됩니다.

다음은 C로 작성된 이진 검색 알고리즘의 간단한 예입니다.

 #include int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right - left) 2; if (arr[mid]="=" target) return mid; } else < left="mid" 1; right="mid" -1; target not found main() arr[]="{1," 3, 5, 7, 9}; n="sizeof(arr)" sizeof(arr[0]); index="binary_search(arr," 0, 1, target); (index="=" -1) printf('target found
'); at %d
', index); 0; pre> <p> <strong>Output:</strong> </p> <pre> Target found at index 2 </pre> <ul> <li>The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.</li> <li>The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message &apos;Target not found&apos; is displayed.</li> <li>The binary search algorithm&apos;s implementation is basic. We begin by setting the left border to the array&apos;s initial index and the right boundary to the array&apos;s last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index&apos;s floor.</li> <li>The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.</li> <li>The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.</li> <li>Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.</li> </ul> <h3>Advantages:</h3> <ul> <li>For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.</li> <li>The algorithm is simple to implement in almost all programming languages.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>Before using the binary search technique, the input array must be sorted, which takes more time and memory.</li> <li>The algorithm cannot be applied to unsorted arrays.</li> <li>The algorithm may yield inaccurate results if the input array is not sorted.</li> <li>The binary search algorithm is not appropriate for tiny datasets since the technique&apos;s overhead may outweigh its benefits.</li> </ul> <h2>Conclusion:</h2> <p>A sorted array can be quickly searched for a specific element using the binary search technique. It employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing it to be highly efficient for large datasets. However, before using the binary search technique, the input array must be sorted, which takes extra time and memory. The binary search algorithm is a sophisticated data processing tool that is widely utilised in various sectors.</p> <hr></=>

Binary_search 함수는 검색할 배열, 왼쪽 및 오른쪽 검색 범위 경계, 찾을 대상 값이라는 네 가지 인수를 허용합니다. 원하는 값을 찾을 수 있으면 함수는 인덱스를 반환합니다. 그렇지 않으면 -1을 반환합니다.
main 함수는 배열 arr과 값 target을 생성합니다. 그런 다음 bin_search 함수를 사용하여 배열에서 원하는 값을 검색합니다. 이 함수는 대상 값이 있는 경우 해당 위치의 인덱스를 반환하고, 해당 값이 발견된 인덱스를 반환합니다. 그렇지 않으면 '대상을 찾을 수 없습니다'라는 메시지가 표시됩니다.
이진 검색 알고리즘의 구현은 기본입니다. 왼쪽 경계를 배열의 초기 인덱스로 설정하고 오른쪽 경계를 배열의 마지막 인덱스로 설정하는 것으로 시작합니다. 왼쪽 경계가 오른쪽 경계보다 작거나 같으면 배열이 한 번 더 반복됩니다. 루프 내에서 공식 (왼쪽 + 오른쪽) / 2를 사용하여 검색 범위의 중간 인덱스를 계산합니다. 이 공식은 중간 지수 바닥의 정수 값을 계산합니다.
배열의 중앙 멤버는 대상 값과 대조됩니다. 동일한 경우 중간 요소의 인덱스를 반환합니다. 원하는 값이 중간 요소보다 작은 경우 오른쪽 경계를 중간 인덱스보다 1 작은 값으로 변경합니다. 그렇지 않은 경우 왼쪽 테두리를 중앙 인덱스보다 하나 더 많이 조정합니다. 목표값을 얻거나 검색 공간이 채워질 때까지 이 작업을 계속합니다.
n이 배열 크기인 이진 검색 알고리즘의 시간 복잡도는 O(log n)입니다. 이는 시간적 복잡도가 O(n)인 선형 검색보다 훨씬 효율적입니다. 여기서 n은 배열의 크기입니다.
마지막으로 이진 검색 기술은 정렬된 배열에서 특정 구성원을 찾는 유용한 방법을 제공합니다. 구축하기 쉽고 O(log n) 시간 복잡도를 가지므로 대규모 데이터 세트에 효율적인 접근 방식입니다.

장점:

대규모 데이터 세트의 경우 이진 검색 알고리즘은 매우 효율적이며 광범위한 입력 크기를 처리할 수 있습니다.
이 알고리즘은 거의 모든 프로그래밍 언어에서 구현하기가 간단합니다.

단점:

이진 검색 기술을 사용하기 전에 입력 배열을 정렬해야 하며 이는 더 많은 시간과 메모리를 필요로 합니다.
정렬되지 않은 배열에는 알고리즘을 적용할 수 없습니다.
입력 배열이 정렬되지 않으면 알고리즘에서 부정확한 결과가 나올 수 있습니다.
이진 검색 알고리즘은 기술의 오버헤드가 이점보다 클 수 있으므로 작은 데이터 세트에는 적합하지 않습니다.

결론:

이진 검색 기술을 사용하면 정렬된 배열에서 특정 요소를 빠르게 검색할 수 있습니다. 분할 정복 전략을 사용하여 반복할 때마다 검색 범위를 절반으로 줄여 대규모 데이터세트에 매우 효율적입니다. 그러나 이진 검색 기술을 사용하기 전에 입력 배열을 정렬해야 하므로 추가 시간과 메모리가 필요합니다. 이진 검색 알고리즘은 다양한 분야에서 널리 활용되는 정교한 데이터 처리 도구입니다.