이진 검색 에 작동하는 검색 기술입니다. 분할 정복 접근 방식 . 정렬된 배열에서 요소를 검색하는 데 사용됩니다. 선형 검색과 비교할 때 이진 검색은 O(logN)의 시간 복잡도로 훨씬 빠르며 선형 검색은 O(N) 시간 복잡도에서 작동합니다.
복합 기본 키
예 :
Input : arr[] = {1, 3, 5, 7, 8, 9}, x = 5 Output : Element found! Input : arr[] = {1, 3, 5, 7, 8, 9}, x = 6 Output : Element not found!> 메모: 배열이 정렬되었다고 가정합니다.
JavaScript에서 이진 검색을 수행하는 방법은 다음과 같습니다.
내용의 테이블
재귀적 접근 방식:
- 기본 조건: 시작 인덱스가 종료 인덱스보다 크면 false를 반환합니다.
- 중간 인덱스를 계산합니다.
- 중간 요소를 숫자 x와 비교합니다. 같으면 true를 반환합니다.
- 더 큰 경우 종료 인덱스 = middle-1로 동일한 함수를 호출하고 1단계를 반복합니다.
- 더 작은 경우 시작 인덱스 = middle+1로 동일한 함수를 호출하고 1단계를 반복합니다.
예: 이 예에서는 위에서 설명한 접근 방식을 사용하는 방법을 보여줍니다.
자바스크립트
let recursiveFunction =>function> (arr, x, start, end) {> >// Base Condition> >if> (start>끝)>return> false>;> >// Find the middle index> >let mid = Math.floor((start + end) / 2);> >// Compare mid with given key x> >if> (arr[mid] === x)>return> true>;> >// If element at mid is greater than x,> >// search in the left half of mid> >if> (arr[mid]>x)> >return> recursiveFunction(arr, x, start, mid - 1);> >else> >// If element at mid is smaller than x,> >// search in the right half of mid> >return> recursiveFunction(arr, x, mid + 1, end);> }> // Driver code> let arr = [1, 3, 5, 7, 8, 9];> let x = 5;> if> (recursiveFunction(arr, x, 0, arr.length - 1)) {> >console.log(>'Element found!'>);> }> else> { console.log(>'Element not found!'>); }> x = 6;> if> (recursiveFunction(arr, x, 0, arr.length - 1)) {> >console.log(>'Element found!'>);> }> else> { console.log(>'Element not found!'>); }> |
자바스크립트 연산자
>
>산출
Element found! Element not found!>
시간 복잡도: 오(로그N)
보조 공간: 오(1)
반복적 접근 방식:
이 반복 접근 방식에서는 재귀 대신 while 루프를 사용하고 루프는 기본 조건에 도달할 때까지, 즉 시작이 끝보다 커질 때까지 실행됩니다.
javafx 튜토리얼
예: 이 예에서는 위에서 설명한 접근 방식을 사용하는 방법을 보여줍니다.
자바스크립트
// Iterative function to implement Binary Search> let iterativeFunction =>function> (arr, x) {> >let start = 0, end = arr.length - 1;> >// Iterate while start not meets end> >while> (start <= end) {> >// Find the mid index> >let mid = Math.floor((start + end) / 2);> >// If element is present at> >// mid, return True> >if> (arr[mid] === x)>return> true>;> >// Else look in left or> >// right half accordingly> >else> if> (arr[mid] start = mid + 1; else end = mid - 1; } return false; } // Driver code let arr = [1, 3, 5, 7, 8, 9]; let x = 5; if (iterativeFunction(arr, x, 0, arr.length - 1)) { console.log('Element found!'); } else { console.log('Element not found!'); } x = 8; if (iterativeFunction(arr, x, 0, arr.length - 1)) { console.log('Element found!'); } else { console.log('Element not found!'); }> |
>
>
워드에 워터마크 삽입산출
Element found! Element found!>
시간 복잡도: O(로그N).
보조 공간: 오(1)