Algorithms 101: Search Algorithms

Search Algorithms

Search algorithms are designed to retrieve information stored within some data structure or calculated in the search space of a problem domain:

Linear Search

Linear search is a simple search algorithm that checks every element in the list until it finds the target value.

def linear_search(arr, target):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Check if the current element is the target
        if arr[i] == target:
            return i  # Return the index of the target element
    return -1  # Return -1 if the target is not found

# Example usage
example_array = [2, 4, 0, 1, 9]
target_value = 1
result = linear_search(example_array, target_value)
if result != -1:
    print(f"Element found at index: {result}")
else:
    print("Element not found")

Code Explanation

1. Function Definition: We define a function linear_search that takes a list arr and a target value as its parameters.

2. Traverse Elements: We run a loop from 0 to len(arr)-1 to traverse each element in the list.

3. Check Condition: Inside the loop, we check if the current element arr[i] is equal to the target value.

4. Return Index: If the current element is the target value, we return the index i.

5. Target Not Found: If the loop completes without finding the target, we return -1 indicating that the target is not in the list.

6. Example Usage: We create an example list, define a target value, search for it using linear_search, and print the result.

Binary Search

Binary search is a more efficient algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        # If target is greater, ignore the left half
        elif arr[mid] < target:
            low = mid + 1
        # If target is smaller, ignore the right half
        else:
            high = mid - 1
    # Target is not present in array
    return -1

# Example usage
example_array = [2, 3, 4, 10, 40]
target_value = 10
result = binary_search(example_array, target_value)
if result != -1:
    print(f"Element found at index: {result}")
else:
    print("Element not found")

Code Explanation

1. Function Definition: We define a function binary_search that takes a sorted list arr and a target value as its parameters.

2. Initialize Variables: We initialize two variables, low and high, to represent the current search range within the list.

3. While Loop: We use a while loop to continue searching as long as low is less than or equal to high.

4. Calculate Midpoint: Inside the loop, we calculate the midpoint mid of the current search range.

5. Check Midpoint: We check if the element at the midpoint arr[mid] is equal to the target. If it is, we return the midpoint index mid.

6. Adjust Search Range: If the target is greater than the midpoint element, we ignore the left half by setting low to mid + 1. If the target is smaller, we ignore the right half by setting high to mid - 1.

7. Target Not Found: If the loop completes without finding the target, we return -1 indicating that the target is not in the list.

8. Example Usage: We create a sorted example list, define a target value, search for it using binary_search, and print the result.