Examples of Linear and Binary Search Problems

3.1 Finding an Element in an Array Using Linear Search

Problem: Given an array of numbers. You need to find the index of a given number using linear search. If the number isn't found, return -1.

Example:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Example of usage:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} found at index {result}")  # Output: Element 7 found at index 2

# Example of usage for an element not present in the array:
target = 5
result = linear_search(arr, target)
print(f"Element {target} found at index {result}")  # Output: Element 5 found at index -1

Explanation:

• The linear_search function goes through each element of the array arr and compares it with target.
• If the element is found, its index is returned.
• If all elements are checked and the desired value isn't found, the function returns -1.

Step-by-step execution:

1. Array [4, 2, 7, 1, 9, 3] and target value 7.
2. Start search: comparing the first element (4) with 7 — doesn't match.
3. Move to the next element (2) — doesn't match.
4. Move to the next element (7) — matches.
5. Return index 2.

3.2 Finding an Element in a Sorted Array Using Binary Search

Problem: Given a sorted array of numbers. You need to find the index of a given number using binary search. If the number isn't found, return -1.

Example:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example of usage:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} found at index {result}")  # Output: Element 7 found at index 3

# Example of usage for an element not present in the array:
target = 6
result = binary_search(sorted_array, target)
print(f"Element {target} found at index {result}")  # Output: Element 6 found at index -1

Explanation:

• The binary_search function uses two pointers (left and right) to track the search boundaries in the array arr.
• At each iteration, the middle element of the array is found and compared with target.
• If the middle element equals target, its index is returned.
• If target is less than the middle element, the search continues in the left half of the array.
• If target is greater than the middle element, the search continues in the right half of the array.
• If the boundaries cross and the element isn't found, -1 is returned.

Step-by-step execution:

1. Sorted array [1, 3, 5, 7, 9, 11, 13] and target value 7.
2. Initial search boundaries: left = 0, right = 6.
3. Find the middle element: mid = (0 + 6) // 2 = 3.
4. Compare the middle element (7) with target (7) — matches.
5. Return index 3.

3.3 Comparison and Selection of Suitable Search Algorithm for Various Tasks

Comparison of linear and binary search:

Selecting the Right Algorithm

Linear Search:

• Used when the data is unsorted.
• Suitable for small arrays or lists.
• Used when the number of elements is small and execution time isn't critical.

Binary Search:

• Used when the data is sorted.
• Ideal for large arrays where search speed matters.
• Efficient if frequent searches are needed in the same data set (the data can be pre-sorted).

3.4 Practical Exercises to Reinforce the Material

Exercise 1: Linear Search

Given an array of numbers. Write a function to search for a given number using linear search. The function should return the index of the found element or -1 if the element isn't found.

Example:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Example of usage:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} found at index {result}")  # Output: Element 7 found at index 2

# Additional tests:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Exercise 2: Binary Search

Given a sorted array of numbers. Write a function to search for a given number using binary search. The function should return the index of the found element or -1 if the element isn't found.

Example:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example of usage:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} found at index {result}")  # Output: Element 7 found at index 3

# Additional tests:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Exercise 3: Comparison of Linear and Binary Search

Given an array of numbers. Write two functions to search for a given number: one using linear search, the other using binary search. Compare the performance of both functions on large arrays.

Example:

import time
import random

# Linear search
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Binary search
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Generate large array
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Compare performance
start_time = time.time()
linear_search(large_array, target)
print(f"Linear search took: {time.time() - start_time:.6f} seconds")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Binary search took: {time.time() - start_time:.6f} seconds")