// Javascript program to implement Jump Search function jumpSearch(arr, x, n) { // Finding block size to be jumped let step = Math.sqrt(n); // Finding the block where element is // present (if it is present) let prev = 0; while (arr[Math.min(step, n)-1] < x) { prev = step; step += Math.sqrt(n); if (prev >= n) return -1; } // Doing a linear search for x in block // beginning with prev. while (arr[prev] < x) { prev++; // If we reached next block or end of // array, element is not present. if (prev == Math.min(step, n)) return -1; } // If element is found if (arr[prev] == x) return prev; return -1; } // Driver program to test function let arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]; let x = 55; let n = arr.length; // Find the index of 'x' using Jump Search let index = jumpSearch(arr, x, n); // Print the index where 'x' is located document.write(`Number ${x} is at index ${index}`);
과 마찬가지로 점프 검색은 정렬된 배열에 대한 검색 알고리즘입니다. 기본 아이디어는 고정된 단계로 건너뛰거나 모든 요소를 검색하는 대신 일부 요소를 건너뛰어
보다 적은 수의 요소를 확인하는 것 입니다.
예를 들어 크기가 n이고 블록(점프할) 크기가 m인 배열 arr[]이 있다고 가정합니다. 그런 다음 인덱스에서 검색합니다. 구간(arr[km] < x < arr[(k+1)m])을 찾으면 인덱스 km에서 선형 검색 작업을 수행하여 요소 x를 찾습니다.
(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610) 배열을 생각해 봅시다. 배열의 길이는 16입니다. 점프 검색은 점프할 블록 크기가 4라고 가정하고 다음 단계에 따라 값 55를 찾습니다.
1단계: 인덱스 0에서 인덱스 4로 점프합니다.
2단계: 인덱스 4에서 인덱스 8로 이동합니다.
3단계: 인덱스 8에서 인덱스 12로 이동합니다.
4단계: 인덱스 12의 요소가 55보다 크므로 인덱스 8로 다시 이동합니다
. 5단계: 요소 55를 얻기 위해 인덱스 8에서 선형 검색을 수행
합니다. 건너뛸 최적의 블록 크기는 얼마입니까?
최악의 경우 n/m 점프를 해야 하고 마지막으로 확인된 값이 검색할 요소보다 크면 선형 검색을 위해 m-1 비교를 더 수행합니다. 따라서 최악의 경우 총 비교 횟수는 ((n/m) + m-1)입니다. 함수((n/m) + m-1)의 값은 m = √n일 때 최소가 됩니다. 따라서 가장 좋은 단계 크기는 m =
√n입니다.
중요 사항:
- 정렬된 배열만 작동합니다.
- 점프할 블록의 최적 크기는 (√ n)입니다. 이것은 점프 탐색의 시간 복잡도를 O(√ n)으로 만든다.
- 점프 검색의 시간 복잡도는 선형 검색( O(n) )과 이진 검색( O(Log n) ) 사이입니다.
- 이진 검색은 점프 검색보다 낫지만 점프 검색은 한 번만 다시 트래버스한다는 장점이 있습니다(이진 검색은 최대 O(Log n) 점프가 필요할 수 있습니다. 검색할 요소가 가장 작은 요소이거나 다음보다 작은 상황을 고려하십시오. 가장 작은). 따라서 이진 검색에 비용이 많이 드는 시스템에서는 점프 검색을 사용합니다.