Skip to main content

Skip List Search

Skip List Search is an advanced search algorithm that combines elements of linked lists and binary search trees to efficiently search through sorted data. Skip Lists use multiple levels of linked lists with increasingly sparse elements, allowing for fast search, insertion, and deletion operations.

  1. Start at the top level: Begin the search at the highest level of the skip list.
  2. Traverse horizontally: Move forward until the next element is greater than or equal to the target.
  3. Move down a level: If the target is not found, move down to the next level and repeat the horizontal traversal.
  4. Repeat: Continue the process until the lowest level is reached.
  5. Check for the target: If the target is found at any level, return its position. If the target is not found after reaching the lowest level, return -1.

How does Skip List Search work?

  • Skip Lists are constructed with multiple layers where each layer is a subset of the layer below it.
  • The top layer is the sparsest, while the bottom layer contains all the elements.
  • Searching starts from the top layer and progresses horizontally and vertically, narrowing down the search range efficiently.

Problem Description

Given a skip list and a target element, implement the Skip List Search algorithm to find the position of the target element. If the element is not present, return -1.

Examples

Example 1: Input: skip_list = [[1, 3, 5, 7, 9], [1, 3, 7], [1]] target = 5 Output: 2

Example 2: Input: skip_list = [[2, 4, 6, 8, 10], [2, 6], [2]] target = 7 Output: -1

Your Task

Complete the function skip_list_search() which takes a 2D array skip_list and an integer target as input parameters and returns the index of the target element. If the element is not present, return -1.

Expected Time Complexity: O(logn)O(\log n) Expected Auxiliary Space: O(n)O(n)

Constraints

  • 1<=n<=1051 <= n <= 10^5
  • 1<=skiplist[i]<=1061 <= skip_list[i] <= 10^6
  • 1<=target<=1061 <= target <= 10^6

Implementation

class Node:
def __init__(self, value=None, right=None, down=None):
self.value = value
self.right = right
self.down = down

class SkipList:
def __init__(self):
self.head = Node()

def search(self, target):
current = self.head
while current:
while current.right and current.right.value < target:
current = current.right
if current.right and current.right.value == target:
return True
current = current.down
return False

# Example usage:
skip_list = SkipList()
# Add elements to skip_list...
print(skip_list.search(5)) # Output: True or False

Complexity Analysis

Time Complexity: O(logn)O(\log n), where nn is the number of elements in the list. Skip List Search provides a logarithmic time complexity by reducing the number of elements to check at each level.

Space Complexity: O(n)O(n), as it requires additional space to store the multiple levels of linked lists.

Advantages and Disadvantages

Advantages:

Faster search times compared to linear search.

Easier to implement and maintain compared to balanced trees like AVL or Red-Black trees.

Allows for efficient insertion and deletion operations.

Disadvantages:

Requires extra space to maintain the skip list levels.

Performance can degrade if the levels are not well-balanced. References Wikipedia: Skip List Geeks for Geeks: Skip List