Skip to main content

Adaptive Segment Search Algorithm (Geeks for Geeks)

Adaptive Segment Search is a sophisticated search algorithm designed to efficiently locate an element in a sorted array. It adapts its search strategy based on the distribution of the elements, making it more efficient than traditional search algorithms in certain scenarios.

  1. Initialization:

    • Divide the array into segments of varying sizes based on the distribution of the elements.
    • Start with the first segment.
  2. Segment Search:

    • Check if the target element falls within the current segment.
    • If it does, perform a linear or binary search within the segment.
    • If not, move to the next segment and repeat the process.
  3. Adaptation:

    • Adjust the segment sizes dynamically based on the distribution of the elements encountered during the search.
  4. Termination:

    • If the target element is found, return its index.
    • If the end of the array is reached without finding the target, return -1.

How does Adaptive Segment Search work?

  • The algorithm starts by dividing the array into segments.
  • It then adapts its search strategy based on the segments and the distribution of elements within the segments.
  • By adjusting the segment sizes dynamically, the algorithm can achieve better performance compared to static segment sizes.

Problem Description

Given a sorted list and a target element, implement the Adaptive Segment 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 = [3, 6, 8, 12, 14, 17, 19, 23, 25, 29] target = 17 Output: 5

Example 2: Input: list = [3, 6, 8, 12, 14, 17, 19, 23, 25, 29] target = 10 Output: -1

Your Task:

You don't need to read input or print anything. Complete the function adaptive_segment_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) in the best case 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


def adaptive_segment_search(arr, n, x):
segment_size = 1
while segment_size < n:
segment_size *= 2

start = 0
while start < n:
end = min(start + segment_size, n)
if arr[end - 1] >= x:
for i in range(start, end):
if arr[i] == x:
return i
return -1
start = end
return -1

Complexity Analysis

Time Complexity:

O(logn)O(\log n) in the best case, where nn is the number of elements in the list.

Space Complexity:

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

Advantages and Disadvantages

Advantages:

Adapts to the distribution of elements in the array.

Can achieve better performance than traditional search algorithms for certain data distributions.

Disadvantages:

Requires the list to be sorted. Complexity may vary based on the distribution of the elements.