Autor: Codenga 25.06.2024

The study of search algorithms often begins with two popular versions: linear search and binary search. These simple algorithms serve as an excellent introduction to the topic of searching.

In this article, we will show you how linear and binary search work and discuss example implementations in Python.

What is Linear Search?

Linear search is a simple method for finding an element in a data collection. The method involves checking each element sequentially, starting from the beginning, until the desired element is found or the end of the collection is reached.

Step-by-step Linear Search

1. Start from the first element in the collection.
2. Check if this element is the one you are looking for.
3. If YES, end the search and return the position of this element.
4. If NO, move to the next element.
5. Repeat steps 2-4 until you find the desired element or reach the end of the collection.

Example Implementation in Python

Let's analyze a simple example that searches for the position of a number in a list. Look at the following solution:

def search_element_position(collection, element):
for i in range(len(collection)):
    if collection[i] == element:
        return i
return None
    
digits = [3, 5, 1, 7, 4]
element = 7
pos = search_element_position(digits, element)
    
print(pos)

The code is quite simple. We have a function called search_element_position(). It takes two parameters: the list to be searched and the value we are looking for. If the value is not found, the function returns None.

Using a loop, we go through all the indices in the list and check sequentially if the element at a given index is equal to the value we are looking for. The result from our example is 3. This means that the value 7 is located at index number 3 (indices, of course, are numbered from 0).

Linear Search - Pros and Cons

The main advantage of linear search is its simplicity – it can be implemented using basic constructs like loops or conditional statements.

The drawback is limited efficiency. Such a search forces us to scan the entire collection from start to finish, which can take a lot of time for a long list.

What is Binary Search?

Binary search operates on the principle of dividing the collection in half and comparing the desired element with the middle element of the collection. If the element is smaller than the middle element, the left half is searched. If the element is larger, the right half is searched. This process repeats until the sublist has no elements.

That’s why this type of search is sometimes called half-interval search.

Step-by-step Binary Search

1. Find the middle element of the list.
2. If the middle element is the desired element, end the search.
3. If the desired element is smaller than the middle element, search the left half of the list.
4. If the desired element is larger than the middle element, search the right half of the list.
5. Repeat steps 1-4 until the element is found or the sublist is empty.

Example Implementation in Python

As usual, it’s worth showing an example implementation. Here is our code:

def binary_search(collection, element):
low = 0
high = len(collection) - 1
    
while low <= high:
    mid = (low + high) // 2
    guess = collection[mid]
    
    if guess == element:
        return mid
    if guess > element:
        high = mid - 1
    else:
        low = mid + 1
    
return None
    
sorted_list = [1, 3, 5, 7, 9]
element = 7
result = binary_search(sorted_list, element)
    
print(result)

The result is the same as in the previous example: the desired element is located at position 3.

The binary search algorithm operates on a sorted list, dividing the search range in half in each iteration. It initially sets the lower (low) and upper (high) indices of the list. In the while loop, as long as the lower index is less than or equal to the upper index, it calculates the middle index (mid) and checks if the element at this index (guess) is equal to the desired element. If so, it returns the index. If the guess is greater than the desired element, it limits the search range to the left half of the list by updating high. Otherwise, it limits the range to the right half by updating low. If the element is not found, it returns None.

Binary Search - Pros and Cons

For large data sets, binary search is more efficient than linear search. However, it requires the data to be sorted beforehand. For very small data sets, linear search might be faster.