- vừa được xem lúc

Jump Search

0 0 26

Người đăng: Sujoy Datta

Theo Viblo Asia

Searching and sorting is always one of the main thing to know and improve about. Like sorting, searching also get special attention from the computer scientists. Today we will learn about a special searching algorithm named Jump sort.

Jump Search

In the vast world of computation, jump search refsembles to a search algorithm for ordered lists. It functions by first checking all items at the edge of block item where m is the size of the block. When an item is found that is larger than the search key, then we do the linear size to find the exact location of the item. The optimal value of m is √n, where n is the length of the list L. Because both steps of the algorithm look at, at most, √n items the algorithm runs in O(√n) time. This number signifies its betterness than linear search and worse than binary search. The main merit over the binary search is that a jump search only needs to jump backwards once, while a binary can jump backwards up to log n times. This can be a key point if a jumping backwards takes significantly more time than jumping forward.

Algorithm

Below is the general algorithm for jump search implementation:

Input: sorted array A with n elements

Output: The index of searched item or -1

The steps for this mechanism are:

  1. Set the starting index, i to 0 and step size,m to √n.

  2. Make a comparison between A[i] with item. If A[i] != item and A[i] < item, then jump to the next block. Also, do the following:

    Reset index, i = step size,m
    Increment step size, m by √n
    
  3. Repeat the step 2 untill m comes to the end of given array.

  4. If A[i] > item, then move to the beginning of the current block and perform a linear search.

    Set start of linear search, x = i
    Compare A[x] with item. If A[x]== item, then print x as the valid location else increment x by 1
    
  5. Continue this procedure untill x comes to the end of step block. and return -1 as not found

Implementation

Below is the ruby implementation of jump search

def jump_search array, item n = array.size i = 0 m = Math.sqrt n while array[m] <= item && m < n do i = m m += Math.sqrt n return -1 if m > n - 1 end start = i while start < m do return x if a[x] == item start += 1 end -1
end

Complexity

We determine the time and space complexity in the following:

Time Complexity:

The while loop in the above code executes n/m times as the loop counter increments by m times in every iteration. Since the optimal value of m= √n , thus, n/m=√n resulting in a time complexity of O(√n).

Space Complexity:

The space complexity of this algorithm is O(1) since it does not requireany other data structure for its implementation.

More Optimal Jump Search

Certainly the execution time of this algorithm is O(√n), There is an improvement section for this algorithm too. if we carefully see, once we know the interval where the value is we can optimize it by applying jump search again on that interval. For example let’s say the list length is 1,000. The jump interval should be: √1000=32. Since we can see closely, we can use jump search with a new step √32≈6. Every time we find the desired interval we can adopt the jump search algorithm with more smaller step. Finally the step will be 1. In that case the complexity of the algorithm does not stuck to O(√n). Now its complexity is more close to logarithmic value. The drawback of this approach is that the implementation of this approach is considered to be more difficult than the binary search, where the complexity is also O(log(n)).

Although it is not netter than binary search in terms of complexity and cannot work without sorted list, still i think it is good one to learn and apply in applicable space. So you can study more if you get some interest. Thank you

Reference: https://www.tutorialspoint.com/Jump-Search

Bình luận

Bài viết tương tự

- vừa được xem lúc

Bài toán tìm đường đi ngắn nhất với giải thuật Dijkstra

Với các bạn sinh viên chuyên ngành công nghệ thông tin, chắc không lạ gì với bài toán tìm đường đi ngắn nhất (Shortest Path Problems) trong đồ thị trọng số nữa. Ở bài viết lần này, mình sẽ làm 3 việc:.

0 0 122

- vừa được xem lúc

Tôi cá là bạn không biết những điều này - Ruby on rails ( Phần 2)

Các bạn có thể theo dõi phần 1 ở đây :. https://viblo.asia/p/toi-ca-la-ban-khong-biet-nhung-dieu-nay-ruby-on-rails-phan-1-WAyK8DDeKxX. 5.

0 0 210

- vừa được xem lúc

Những thay đổi trong ruby 3.0

. 2020 là một năm lớn đối với cộng đồng Ruby. Những người sáng lập Ruby có một món quà thực sự tuyệt vời cho chúng ta vào giáng sinh với việc phát hành Ruby 3.

0 0 31

- vừa được xem lúc

Có gì đặc biệt trong phiên bản Ruby 3x3 ?

Hello guys, chắc hẳn thời gian vừa rồi chúng ta cũng đã nghe qua thông tin Ruby sắp cho ra mắt Ruby version 3, hay còn được gọi là ruby 3x3, vậy liệu Ruby version 3 này có gì mới, và có những update nào đáng phải kể đến, và tại sao mọi người lại gọi nó là ruby version 3x3, thì trong bài ngày hôm nay

0 0 30

- vừa được xem lúc

Cách sử dụng class Time & Date trong Ruby (Phần 1)

Time là một class trong Ruby, nó sẽ giúp chỉnh sửa format, trích xuất thông tin một cách hiệu quả theo ý của bạn. . Topic hôm nay chúng ta có gì nào. .

0 0 83

- vừa được xem lúc

Ruby 3.0 có gì mới

Ruby 3.0.0 đã được ra mới được ra mắt vào tháng 12/2020, mục tiêu của bản 3.0.

0 0 26