이번 포스팅에서는 이진 검색 알고리즘에 대해 알아보겠습니다. 검색은 목록에서 특정 요소를 찾는 프로세스입니다. 요소가 목록에 있으면 프로세스가 성공이라고 하며 프로세스는 해당 요소의 위치를 반환합니다. 그렇지 않으면 검색이 실패했다고 합니다.
선형 검색과 이진 검색은 널리 사용되는 두 가지 검색 기술입니다. 여기서는 이진 검색 알고리즘에 대해 설명합니다.
이진 검색은 정렬된 목록에서 효율적으로 작동하는 검색 기술입니다. 따라서 이진 검색 기술을 사용하여 요소를 목록으로 검색하려면 목록이 정렬되어 있는지 확인해야 합니다.
이진 검색은 목록을 두 부분으로 나누고 항목을 목록의 중간 요소와 비교하는 분할 정복 접근 방식을 따릅니다. 일치하는 항목이 발견되면 중간 요소의 위치가 반환됩니다. 그렇지 않으면 경기를 통해 생성된 결과에 따라 절반 중 하나를 검색합니다.
알파벳에 대한 숫자
참고: 정렬된 배열 요소에 대해 이진 검색을 구현할 수 있습니다. 목록 요소가 정렬된 방식으로 정렬되지 않은 경우 먼저 정렬해야 합니다.
이제 이진 검색의 알고리즘을 살펴보겠습니다.
연산
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
바이너리 검색 작업
이제 이진 검색 알고리즘의 작동을 살펴보겠습니다.
이진 검색 알고리즘의 작동을 이해하기 위해 정렬된 배열을 살펴보겠습니다. 예제를 통해 이진 검색의 작동 방식을 쉽게 이해할 수 있습니다.
이진 검색 알고리즘을 구현하는 방법에는 두 가지가 있습니다.
- 반복적 방법
- 재귀적 방법
이진 검색의 재귀적 방법은 분할 정복 접근 방식을 따릅니다.
인터넷의 단점
배열의 요소는 다음과 같습니다.
검색할 요소는 다음과 같습니다. 케이 = 56
우리는 아래 공식을 사용하여 계산해야 합니다. 중반 배열의 -
mid = (beg + end)/2
따라서 주어진 배열에서 -
빌다 = 0
끝 = 8
stlc
중반 = (0 + 8)/2 = 4. 따라서 4는 배열의 중간입니다.
이제 검색할 요소를 찾았습니다. 따라서 알고리즘은 일치하는 요소의 인덱스를 반환합니다.
이진 검색 복잡성
이제 최상의 경우, 평균적인 경우, 최악의 경우에서 이진 검색의 시간 복잡도를 살펴보겠습니다. 또한 이진 검색의 공간 복잡도도 살펴보겠습니다.
1. 시간 복잡도
| 사례 | 시간 복잡도 |
|---|---|
| 최선의 경우 | 오(1) |
| 평균 사례 | 오(로그인) |
| 최악의 경우 | 오(로그인) |
2. 공간 복잡성
| 공간 복잡도 | 오(1) |
- 이진 검색의 공간 복잡도는 O(1)입니다.
이진 검색 구현
이제 다양한 프로그래밍 언어로 된 이진 검색 프로그램을 살펴보겠습니다.
프로그램: C 언어로 이진 검색을 구현하는 프로그램을 작성하세요.
자바 기초
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> 산출
이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.