#!/usr/bin/env python
# coding: utf-8

# ## ```Q3.``` ##
# 
# ## ```Write a Python program to perform Jump Search for a given key and report success or failure. Prompt the user to enter the key and a list of numbers.``` ##

# ## -----------------------------------------------------------------------------------------------------------------------------

# ## Jump Search##
# 
# Similar to Binary Search, **Jump Search** or **Block Search** is an algorithm only for ordered (sorted) lists. The major idea behind this algorithm is to make less comparisons by skipping a definite amount of elements in between the elements getting compared leading to less time required for the searching process.  
# 
# It can be classified as an improvement of the linear search algorithm since it depends on linear search to perform the actual comparison when searching for a value.   

# ## -----------------------------------------------------------------------------------------------------------------------------

# ## Jump Search Steps ##
# 
# In Jump search, it is not necessary to scan all the elements in the list to find the desired value. We just check an element and if it is less than the desired value, then some of the elements following it are skipped by jumping ahead.  
# 
# After moving a little forward again, the element is checked. If the checked element is greater than the desired value, then we have a boundary and we are sure that the desired value lies between the previously checked element and the currently checked element. However, if the checked element is less than the value being searched for, then we again make a small jump and repeat the process.  
# 
# Given a sorted list, instead of searching through the list elements incrementally, we search by ```jump```. The optimal size for ```jump``` is $\sqrt{N}$ where the ```N``` is the length of the list.    
# 
# So in our input list ```list_of_numbers,``` if we have a jump size of ```jump``` then our algorithm will consider the elements between ```list_of_numbers[0]``` and ```list_of_numbers[0 + number_of_jumps],``` if the key element is not found then we will consider the other elements between ```list_of_numbers[0 + number_of_jumps]``` and ```list_of_numbers[0 + 2*number_of_jumps],``` again if the key element is not found then we consider the elements between ```list_of_numbers[0 + 2*number_of_jumps],``` and ```list_of_numbers[0 + 3*number_of_jumps]``` and so on.   
# 
# With each jump, we store the previous value we looked at and its index. When we find a set of values where ```list_of_numbers[i] < key_element < list_of_numbers[i + number_of_jumps],``` we perform a linear search with ```list_of_numbers[i]``` as the left-most element and ```list_of_numbers[i + number_of_jumps]``` as the right-most element in our search block.  
# 
# For example, consider a list of ```[1, 2, 3, 4, 5, 6, 7, 8, 9].```The length of the list is ```9``` and the size of  ```jump``` is ```3```. If we have to find the key element ```8``` then the following steps are performed using the Jump search technique.   
# 
# ```Step 1:``` First three elements are checked. Since 3 is smaller than 8, we will have to make a jump ahead.    
# 
# <img src="images\4.jpg" alt="jump1" align="middle" height = 250, width = 850>
# 
# ```Step 2:``` Next three elements are checked. Since 6 is smaller than 8, we will have to make a jump ahead.      
# 
# <img src="images\5.jpg" alt="jump1" align="middle" height = 250, width = 850>
# 
# ```Step 3:``` Next three elements are checked. Since 9 is greater than 8, the desired value lies within the current boundary.      
# 
# <img src="images\6.jpg" alt="jump1" align="middle" height = 250, width = 850>
# 
# ```Step 4:``` A linear search is now done to find the value in the array.     

# ## -----------------------------------------------------------------------------------------------------------------------------

# In[8]:


import math


def jump_search(list_of_numbers, key):
    list_length = len(list_of_numbers)

    # Calculate jump size
    jump = int(math.sqrt(list_length))

    left, right = 0, 0  # These are the index values

    # Find the block where key element is present (if it is present)
    while left < list_length and list_of_numbers[left] <= key:
        right = min(list_length - 1, left + jump)
        if list_of_numbers[left] <= key <= list_of_numbers[right]:
            break
        left += jump

    if left >= list_length or list_of_numbers[left] > key:
        return -1

    right = min(list_length - 1, right)
    i = left
    # Do linear search for key element in the block
    while i <= right and list_of_numbers[i] <= key:
        if list_of_numbers[i] == key:
            return i  # Return the position of the key element
        i += 1

    return -1


def user_input():
    list_of_numbers = list()
    total_elements = input("Enter a list of numbers in ascending order with space between each other: ").split()
    for each_element in range(len(total_elements)):
        list_of_numbers.append(int(total_elements[each_element]))

    key = int(input("Enter the Key number to search: "))

    index = jump_search(list_of_numbers, key)
    if index == -1:
        print("Entered key is not present")
    else:
        print(f"Key number {key} is found in Position {index + 1}")


if __name__ == "__main__":
    user_input()


# ## -----------------------------------------------------------------------------------------------------------------------------

# ### Step by Step tracing of the above code
# ```
# Elements -> 1 2 3 4 5 6 7 8 9
# Index    -> 0 1 2 3 4 5 6 7 8
# 
# left = 0
# right = 0
# list_length = 9
# jump = 3
# 
# while 0 < 9 and 1 <= 8:
#     right = min(8, 3)
#     right is 3
#     if 1 <= 8 <= 4 condition is False
#     left = 3
# 
# while 3 < 9 and 4 <= 8:
#     right = min(8, 6)
#     right is 6    
#     if 4 <= 8 <= 7: condition is False
#     left = 6
# 
# while 6 < 9 and 7 <= 8:
#     right = min(8, 9)
#     right is 8
#     if 7 <= 8 <= 9: condition is True
#     break
# 
# right = min(8, 8)
# right is 8
# i = left
# i is 6
# 
# while 6 <= 8 and 7 <= 8:
#     if 7 == 8: condition is False
#     i += 1
#     i is 7
# 
# while 7 <= 8 and 8 <= 8:
#     if 8 == 8:  condition is True
#         return 7 here 7 is the index position and not the actual element
# 
# print -> i + 1 position
# ```