Welcome to our comprehensive guide on Data Structures and Algorithms! Today, we'll delve into the fascinating world of Comparison and Non-Comparison Based data structures. Let's get started! š
Comparison-based data structures sort and search elements based on a comparison of keys or values. They are primarily used in scenarios where we need to find a specific element or elements quickly.
Binary Search is a popular comparison-based algorithm used for searching an element in a sorted list or array. It works by repeatedly dividing the search interval in half.
š Note: Binary Search works only on sorted data.
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1Non-Comparison-based data structures, also known as Hash-based data structures, do not rely on comparing elements to locate them. Instead, they use a hash function to map elements to specific positions in the data structure.
A Hash Table, or Hash Map, is a non-comparison-based data structure that stores data in an array using a hash function. It allows quick lookups, additions, and deletions.
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [None] * size
def hash_function(self, key):
hash = 0
for char in key:
hash = (hash * 37 + ord(char)) % self.size
return hash
def insert(self, key, value):
index = self.hash_function(key)
self.table[index] = (key, value)
def get(self, key):
index = self.hash_function(key)
entry = self.table[index]
if entry:
key, value = entry
return value
return None
# Usage
ht = HashTable()
ht.insert('apple', 1)
ht.insert('banana', 2)
print(ht.get('apple')) # Output: 1
What does a Hash Table primarily use to locate elements?
Which of the following data structures relies on comparison to locate elements? A. Hash Table B. Binary Search Tree C. Linked List Correct: B. Binary Search Tree
Binary Search works on... A. Unsorted data B. Sorted data C. Random data Correct: B. Sorted data
That's all for today! We hope you found this lesson on Comparison vs Non-Comparison Based data structures informative. Stay tuned for more exciting topics! š„³
If you have any questions or need help with anything, feel free to ask. Happy coding! š