점프 검색
좋다 이진 검색 점프 검색(Jump Search)은 정렬된 배열을 검색하는 알고리즘입니다. 기본 아이디어는 (보다 적은 수의 요소를 확인하는 것입니다. 선형 검색 ) 고정된 단계만큼 앞으로 점프하거나 모든 요소를 검색하는 대신 일부 요소를 건너뛰는 방식입니다.
예를 들어 크기 n의 배열 arr[]과 크기 m의 블록(점프 대상)이 있다고 가정합니다. 그런 다음 arr[0] arr[m] arr[2m].....arr[km] 등의 인덱스를 검색합니다. 간격(arr[km])을 찾으면 < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element 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단계: 인덱스 8에서 선형 검색을 수행하여 요소 55를 얻습니다.
선형 및 이진 검색과 비교한 성능:
선형 및 이진 검색과 비교하면 선형 검색보다 낫지만 이진 검색보다 좋지는 않습니다.
성능이 증가하는 순서는 다음과 같습니다.
선형 검색 < jump search < binary search
건너뛸 최적의 블록 크기는 얼마입니까?
최악의 경우 n/m 점프를 수행해야 하며 마지막으로 확인한 값이 검색할 요소보다 큰 경우 선형 검색을 위해 m-1 비교를 더 수행합니다. 따라서 최악의 경우 총 비교 횟수는 ((n/m) + m-1)이 됩니다. 함수의 값 ((n/m) + m-1)은 m = √n일 때 최소가 됩니다. 따라서 가장 좋은 단계 크기는 m = √입니다. N.
알고리즘 단계
- 점프 검색(Jump Search)은 배열의 특정 단계를 점프하여 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.
- 단계는 배열 길이의 sqrt에 의해 결정됩니다.
- 점프 검색을 위한 단계별 알고리즘은 다음과 같습니다.
- 배열 n 길이의 sqrt를 취하여 단계 크기 m을 결정합니다.
- 배열의 첫 번째 요소에서 시작하여 해당 위치의 값이 목표 값보다 커질 때까지 m 단계씩 점프합니다.
목표보다 큰 값이 발견되면 목표를 찾거나 목표가 배열에 없다는 것이 분명해질 때까지 이전 단계부터 선형 검색을 수행합니다.
대상이 발견되면 해당 인덱스를 반환합니다. 그렇지 않으면 -1을 반환하여 배열에서 대상을 찾을 수 없음을 나타냅니다.
예시 1 :
C++ // C++ program to implement Jump Search #include using namespace std ; int jumpSearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int prev = 0 ; while ( arr [ min ( step n ) -1 ] < x ) { prev = step ; step += 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 == min ( step n )) return -1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return -1 ; } // Driver program to test function int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x n ); // Print the index where 'x' is located cout < < ' n Number ' < < x < < ' is at index ' < < index ; return 0 ; } // Contributed by nuclode
C #include #include int min ( int a int b ){ if ( b > a ) return a ; else return b ; } int jumpsearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int prev = 0 ; while ( arr [ min ( step n ) -1 ] < x ) { prev = step ; step += 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 == min ( step n )) return -1 ; } // If element is found if ( arr [ prev ] == x ) return prev ; return -1 ; } int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int index = jumpsearch ( arr x n ); if ( index >= 0 ) printf ( 'Number is at %d index' index ); else printf ( 'Number is not exist in the array' ); return 0 ; } // This code is contributed by Susobhan Akhuli
Java // Java program to implement Jump Search. public class JumpSearch { public static int jumpSearch ( int [] arr int x ) { int n = arr . length ; // Finding block size to be jumped int step = ( int ) Math . floor ( Math . sqrt ( n )); // Finding the block where element is // present (if it is present) int prev = 0 ; for ( int minStep = Math . min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . min ( step n ) - 1 ) { prev = step ; step += ( int ) Math . floor ( 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 public static void main ( String [ ] args ) { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x ); // Print the index where 'x' is located System . out . println ( 'nNumber ' + x + ' is at index ' + index ); } }
Python # Python3 code to implement Jump Search import math def jumpSearch ( arr x n ): # Finding block size to be jumped step = math . sqrt ( n ) # Finding the block where element is # present (if it is present) prev = 0 while arr [ int ( 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 [ int ( prev )] < x : prev += 1 # If we reached next block or end # of array element is not present. if prev == min ( step n ): return - 1 # If element is found if arr [ int ( prev )] == x : return prev return - 1 # Driver code to test function arr = [ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ] x = 55 n = len ( arr ) # Find the index of 'x' using Jump Search index = jumpSearch ( arr x n ) # Print the index where 'x' is located print ( 'Number' x 'is at index' ' %.0f ' % index ) # This code is contributed by 'Sharad_Bhardwaj'.
C# // C# program to implement Jump Search. using System ; public class JumpSearch { public static int jumpSearch ( int [] arr int x ) { int n = arr . Length ; // Finding block size to be jumped int step = ( int ) Math . Sqrt ( n ); // Finding the block where the element is // present (if it is present) int prev = 0 ; for ( int minStep = Math . Min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . Min ( step n ) - 1 ) { prev = step ; step += ( int ) 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 public static void Main () { int [] arr = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x ); // Print the index where 'x' is located Console . Write ( 'Number ' + x + ' is at index ' + index ); } }
JavaScript < script > // 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 ; for ( int minStep = Math . Min ( step n ) - 1 ; arr [ minStep ] < x ; minStep = Math . Min ( step n ) - 1 ) { 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 } ` ); // This code is contributed by _saurabh_jaiswal < /script>
PHP // PHP program to implement Jump Search function jumpSearch ( $arr $x $n ) { // Finding block size to be jumped $step = sqrt ( $n ); // Finding the block where element is // present (if it is present) $prev = 0 ; while ( $arr [ min ( $step $n ) - 1 ] < $x ) { $prev = $step ; $step += 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 == min ( $step $n )) return - 1 ; } // If element is found if ( $arr [ $prev ] == $x ) return $prev ; return - 1 ; } // Driver program to test function $arr = array ( 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ); $x = 55 ; $n = sizeof ( $arr ) / sizeof ( $arr [ 0 ]); // Find the index of '$x' using Jump Search $index = jumpSearch ( $arr $x $n ); // Print the index where '$x' is located echo 'Number ' . $x . ' is at index ' . $index ; return 0 ; ?>
산출:
Number 55 is at index 10
시간복잡도 : O(?n)
보조공간 : O(1)점프 검색의 장점:
- 요소가 균일하게 분포된 배열에 대한 선형 검색보다 낫습니다.
- 점프 검색은 대규모 배열에 대한 선형 검색에 비해 시간 복잡도가 낮습니다.
- 점프 검색에서 수행되는 단계 수는 배열 크기의 제곱근에 비례하므로 대규모 배열에 더 효율적입니다.
- 이진 검색이나 삼항 검색과 같은 다른 검색 알고리즘에 비해 구현하기가 더 쉽습니다.
- 점프 검색은 각 반복마다 배열에서 더 가까운 위치로 점프할 수 있으므로 요소가 순서대로 균일하게 분포된 배열에 적합합니다.
중요 사항:
- 정렬된 배열에서만 작동합니다.
- 점프할 최적의 블록 크기는 (?n)이다. 이는 점프 탐색의 시간 복잡도를 O(?n)로 만든다.
- 점프 검색의 시간 복잡도는 선형 검색((O(n))과 이진 검색(O(Log n)) 사이입니다.
- 이진 검색은 점프 검색보다 낫지만 점프 검색은 한 번만 뒤로 탐색한다는 장점이 있습니다(이진 검색은 검색할 요소가 가장 작은 요소이거나 가장 작은 요소보다 단지 큰 상황을 고려하면 최대 O(Log n) 점프가 필요할 수 있습니다). 따라서 이진 검색에 비용이 많이 드는 시스템에서는 Jump Search를 사용합니다.
참고자료:
https://en.wikipedia.org/wiki/Jump_search
GeeksforGeeks를 좋아하고 기여하고 싶다면 다음을 사용하여 기사를 작성할 수도 있습니다. write.geeksforgeeks.org 또는 기사를 [email protected]로 우편으로 보내세요. GeeksforGeeks 메인 페이지에 나타나는 기사를 보고 다른 Geeks를 도와주세요. 잘못된 내용을 발견했거나 위에서 논의한 주제에 대해 더 많은 정보를 공유하고 싶다면 댓글을 작성해 주세요.
