n개의 요소로 구성된 정렬된 배열 arr[]이 주어지면 arr[]에서 주어진 요소 x를 검색하는 함수를 작성하십시오.
간단한 접근 방식은 선형 검색 을 수행하는 것 입니다.
위 알고리즘의 시간 복잡도는 O(n)입니다. 동일한 작업을 수행하는 또 다른 방법은 이진 검색을 사용하는 것입니다.
이진 검색:
검색 간격을 반으로 반복적으로 나누어 정렬된 배열을 검색합니다. 전체 배열을 포함하는 간격으로 시작합니다. 검색 키의 값이 간격 중간에 있는 항목보다 작으면 간격을 하단으로 좁힙니다. 그렇지 않으면 위쪽 절반으로 좁힙니다. 값을 찾거나 간격이 비어 있을 때까지 반복적으로 확인합니다.
이진 검색의 개념은 배열이 정렬된 정보를 사용하여 시간 복잡도를 O(Log n)으로 줄이는 것입니다.
- x를 중간 요소와 비교합니다.
- x가 중간 요소와 일치하면 중간 인덱스를 반환합니다.
- 그렇지 않으면 x가 중간 요소보다 크면 x는 중간 요소 뒤의 오른쪽 절반 하위 배열에만 있을 수 있습니다. 그래서 우리는 오른쪽 절반에 대해 반복합니다.
- 그렇지 않으면(x가 더 작음) 왼쪽 절반에 대해 반복됩니다.
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1 function binarySearch(arr, l, r, x){ if (r >= l) { let mid = l + Math.floor((r - l) / 2); // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } let arr = [ 2, 3, 4, 10, 40 ]; let x = 10; let n = arr.length let result = binarySearch(arr, 0, n - 1, x); (result == -1) ? document.write( "Element is not present in array") : document.write("Element is present at index " +result);