Python search algorithms list

Stella 43 Published: 07/13/2024

Python search algorithms list

I'll respond in English for you! Here's a comprehensive list of Python search algorithms:

Linear Search: This algorithm iterates over the entire list to find an element, which makes it inefficient for large datasets. However, it's simple and easy to implement.

Example:

    def linear_search(arr, target):

for i in range(len(arr)):


if arr[i] == target:


return i


return -1
Binary Search: This algorithm is used for sorted lists, where the element we're searching for is within the list. It's more efficient than linear search but requires the input to be sorted.

Example:

    def binary_search(arr, target):

low = 0


high = len(arr) - 1


while low <= high:


mid = (low + high) // 2


guess = arr[mid]


if guess == target:


return mid


elif guess > target:


high = mid - 1


else:


low = mid + 1


return -1
Fuzzy Search: This algorithm is used when the search term might not exactly match what's in the dataset, but you still want to find similar results.

Example: (Using Python's fuzzywuzzy library)

    from fuzzywuzzy import process

def fuzzy_search(input, choices):


return process.extractOne(input, choices)[0][1]
Ternary Search: This algorithm is used when the dataset is sorted and we're searching for an element within a specific range.

Example:

    def ternary_search(arr, target, low=0, high=None):

if high is None:


high = len(arr) - 1


while low <= high:


mid1 = (low + high) // 3


mid2 = (2 * (low + high) // 3)


if arr[mid1] == target:


return mid1


elif arr[mid2] == target:


return mid2


elif target < arr[mid1]:


high = mid1 - 1


elif target > arr[mid2]:


low = mid2 + 1


else:


for i in range(low, high+1):


if arr[i] == target:


return i


return -1
Rabin-Karp Search: This algorithm uses the Rabin-Karp string search algorithm to find all occurrences of a given string within another string.

Example: (Using Python's hashlib and string libraries)

    def rabin_karp_search(pattern, text):

d = 256


pattern_len = len(pattern)


text_len = len(text)


lps = [0] * (pattern_len + 1)


j = 0


for i in range(1, pattern_len + 1):


if pattern[i] == pattern[j]:


j += 1


lps[i] = j


elif j != 0:


j = lps[j - 1]


else:


lps[i] = 0


j = 0


for i in range(text_len):


if text[i] == pattern[0]:


k = 1


while k <= pattern_len and i+k < text_len and text[i + k] == pattern[k]:


k += 1


if k == pattern_len:


return "Pattern found at index %d" % (i, )


return "Pattern not found"
Knuth-Morris-Pratt Search: This algorithm is used for searching a string within another string, handling cases where the search string might be a suffix of the original text.

Example: (Using Python's string library)

    def knuth_morris_pratt_search(text, pattern):

m = len(pattern)


n = len(text)


lps = [0] * (m + 1)


j = 0


for i in range(1, m + 1):


if pattern[i] == pattern[j]:


j += 1


lps[i] = j


elif j != 0:


j = lps[j - 1]


else:


lps[i] = 0


j = 0


for i in range(n):


if text[i] == pattern[0]:


k = 1


while k <= m and i + k < n and text[i + k] == pattern[k]:


k += 1


if k == m:


return "Pattern found at index %d" % (i, )


elif k > j:


j = k


return "Pattern not found"
Exponential Search: This algorithm uses the fact that the logarithm of a number grows much faster than its square root or cube root.

Example: (Using Python's math library)

    def exponential_search(arr, target):

n = len(arr)


if n == 0:


return -1


i = int(math.log(n) / math.log(2))


while i >= 1 and arr[i] < target:


i -= 1


for j in range(i + 1, min(i + 7, n)):


if arr[j] == target:


return j


elif j >= i + 5 and arr[j - 5] <= target:


return binary_search(arr, j, target)


return -1
Exhaustive Search: This algorithm iterates over the entire list until it finds the element we're searching for.

Example:

    def exhaustive_search(arr, target):

for i in range(len(arr)):


if arr[i] == target:


return i


return -1

Remember that each algorithm has its strengths and weaknesses, and choosing the right one depends on the specific requirements of your problem.

(Note: These examples are just a starting point, and you may need to modify them to suit your specific use case.)

How to use searching in Python?

I'm happy to help you with that!

In Python, searching is a fundamental task that can be achieved using various libraries and algorithms. Here are some ways to search for data or strings in Python:

Using the in operator: The simplest way to search for an element in a list or a string is by using the in operator. For example: 
   my_list = [1, 2, 3, 4, 5]

target_value = 3


if target_value in my_list:


print(f"'{target_value}' found in the list!")
Using List Comprehensions: If you're searching for a pattern or a specific condition within a list, you can use list comprehensions. For instance: 
   numbers = [1, 2, 3, 4, 5]

even_numbers = [num for num in numbers if num % 2 == 0]


print(even_numbers) # prints: [2, 4]
Using the find() function: If you're searching within a string for a specific pattern or substring, you can use the find() function: 
   my_string = "Hello, world!"

target_substring = "world"


index = my_string.find(target_substring)


if index != -1:


print(f"'{target_substring}' found at index {index}!")
Using Regular Expressions: Python has excellent support for regular expressions through the re module. You can use regex patterns to search for complex patterns in strings, like emails or phone numbers. 
   import re

my_string = "[email protected]"


email_pattern = r"[a-zA-Z0-9_.]+@[a-zA-Z0-9-.]+.[a-zA-Z]{2,}"


match = re.search(email_pattern, my_string)


if match:


print(f"Email pattern found: {match.group()}")
Using Indexing and Slicing: For searching within a string using indexing or slicing, you can use the square brackets [] to access specific characters or substrings. 
   my_string = "Hello, world!"

first_char = my_string[0]


print(f"First character: {first_char}")
Using Binary Search: If your data is sorted and you're searching for a specific element within the list, you can use binary search for efficient searching. 
   numbers = [1, 2, 3, 4, 5]

target_value = 3


def binary_search(arr, target):


low, high = 0, len(arr) - 1


while low <= high:


mid = (low + high) // 2


if arr[mid] == target:


return mid


elif arr[mid] < target:


low = mid + 1


else:


high = mid - 1


return None


index = binary_search(numbers, target_value)


if index is not None:


print(f"'{target_value}' found at index {index}!")

Remember that searching is a fundamental concept in programming, and there are many ways to achieve it. The choice of method often depends on the complexity of your data, the frequency of searches, or specific requirements.

Please let me know if you have any questions or need further clarification!

Related Articles