Skip to main content

Hybrid Jump Binary Search (Geeks for Geeks)

Hybrid Jump Binary Search is an advanced search algorithm that combines the features of Jump Search and Binary Search. It first uses a jump step to find a block where the target element might be present and then performs a binary search within that block to find the target element.

  1. Calculate the optimal step size N\sqrt{N}, where NN is the length of the list.
  2. Start from the first element and jump ahead by the step size until the target element is greater than or equal to the current element.
  3. Once the block where the target might be located is identified, perform a binary search within that block.
  4. If the target element is found, return its index.
  5. If the target element is not found, return -1.

How does Hybrid Jump Binary Search work?

  • It combines jump search and binary search to efficiently locate the target element.
  • Jump search quickly narrows down the possible range of the target element.
  • Binary search is then used within the identified range to find the target element efficiently.

Problem Description

Given a sorted list and a target element, implement the Hybrid Jump Binary Search algorithm to find the index of the target element in the list. If the element is not present, return -1.

Examples

Example 1: Input: list = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100] target = 85 Output: 8

Example 2: Input: list = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100] target = 55 Output: -1

Your Task:

You don't need to read input or print anything. Complete the function hybrid_jump_binary_search() which takes arr[], N and K as input parameters and returns the index of K in the array. If K is not present in the array, return -1.

Expected Time Complexity: O(logN)O(\log N) Expected Auxiliary Space: O(1)O(1)

Constraints

  • 1<=N<=1051 <= N <= 10^5
  • 1<=arr[i]<=1061 <= arr[i] <= 10^6
  • 1<=K<=1061 <= K <= 10^6

Implementation


import math

def binary_search(arr, low, high, x):
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1

def hybrid_jump_binary_search(arr, x):
n = len(arr)
step = int(math.sqrt(n))
prev = 0

while arr[min(step, n) - 1] < x:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1

return binary_search(arr, prev, min(step, n) - 1, x)

Complexity Analysis

Time Complexity:

O(logN)O(\log N), where NN is the number of elements in the list. The combination of jump search and binary search reduces the search space efficiently.

Space Complexity:

O(1)O(1), as no extra space is required apart from the input list.

Advantages and Disadvantages

Advantages:

Efficient for large sorted arrays.

Combines the advantages of both jump search and binary search.

Disadvantages:

Requires the list to be sorted.

Slightly more complex to implement compared to individual search algorithms.