점프 검색 - 기타

좋다 이진 검색 점프 검색(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 << 'nNumber ' << x << ' is at index ' << index;  return 0; } // Contributed by nuclode

#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# 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; ?>

산출:

char tostring 자바

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를 도와주세요. 잘못된 내용을 발견했거나 위에서 논의한 주제에 대해 더 많은 정보를 공유하고 싶다면 댓글을 작성해 주세요.