Searching Problems in Arrays - 10 Must-Do Questions
10 Must-Do Searching Problems in Arrays (with Python Solutions & Examples)

1. Linear Search

Search for an element in an array by checking each element one by one.

Examples:
Input: arr = [10, 20, 30, 40, 50], x = 30 → Output: 2
Input: arr = [5, 15, 25], x = 20 → Output: -1
Input: arr = [7, 8, 9, 10], x = 7 → Output: 0 
def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

print(linear_search([10, 20, 30, 40, 50], 30))  # 2
Scan elements one by one until found. Time Complexity: O(n), Space: O(1).

2. Search all occurrences of an element

Examples:
Input: arr = [1, 2, 3, 2, 4], x = 2 → Output: [1, 3]
Input: arr = [5, 5, 5, 5], x = 5 → Output: [0, 1, 2, 3]
Input: arr = [1, 2, 3], x = 7 → Output: [] 
def search_all_occurrences(arr, x):
    return [i for i in range(len(arr)) if arr[i] == x]

print(search_all_occurrences([1, 2, 3, 2, 4], 2))  # [1, 3]
Collect all indices of x in array. Time Complexity: O(n).

3. Find index of first occurrence

Examples:
Input: arr = [1, 3, 5, 3, 7], x = 3 → Output: 1
Input: arr = [4, 4, 4], x = 4 → Output: 0
Input: arr = [10, 20, 30], x = 25 → Output: -1 
def first_occurrence(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1
Return the index of the first match found. Time Complexity: O(n).

4. Find index of last occurrence

Examples:
Input: arr = [1, 3, 5, 3, 7], x = 3 → Output: 3
Input: arr = [4, 4, 4], x = 4 → Output: 2
Input: arr = [2, 4, 6], x = 8 → Output: -1 
def last_occurrence(arr, x):
    for i in range(len(arr)-1, -1, -1):
        if arr[i] == x:
            return i
    return -1
Start checking from the end. Time Complexity: O(n).

5. Count frequency of an element

Examples:
Input: arr = [1, 2, 2, 3, 2], x = 2 → Output: 3
Input: arr = [10, 20, 30], x = 20 → Output: 1
Input: arr = [5, 6, 7], x = 9 → Output: 0 
def count_frequency(arr, x):
    return arr.count(x)

print(count_frequency([1,2,2,3,2], 2))  # 3
Count occurrences using Python’s count(). Time Complexity: O(n).

6. Check if an element exists

Examples:
Input: arr = [5, 10, 15], x = 10 → Output: Yes
Input: arr = [2, 4, 6], x = 5 → Output: No
Input: arr = [100, 200], x = 300 → Output: No 
def exists(arr, x):
    return "Yes" if x in arr else "No"

print(exists([5, 10, 15], 10))  # Yes
Use Python’s membership operator in. Time Complexity: O(n).

7. Binary Search (Iterative)

Examples:
Input: arr = [1, 3, 5, 7, 9], x = 7 → Output: 3
Input: arr = [2, 4, 6, 8], x = 5 → Output: -1
Input: arr = [10, 20, 30, 40, 50], x = 10 → Output: 0 
def binary_search_iterative(arr, x):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high)//2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1
Works only on sorted arrays. Divide and search halves. Time Complexity: O(log n).

8. Binary Search (Recursive)

Examples:
Input: arr = [1, 2, 3, 4, 5], x = 4 → Output: 3
Input: arr = [10, 20, 30, 40], x = 15 → Output: -1
Input: arr = [7, 8, 9], x = 9 → Output: 2 
def binary_search_recursive(arr, low, high, x):
    if low <= high:
        mid = (low + high)//2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search_recursive(arr, low, mid-1, x)
        else:
            return binary_search_recursive(arr, mid+1, high, x)
    return -1
Recursive version of binary search. Time Complexity: O(log n), Space: O(log n).

9. Find first occurrence using Binary Search

Examples:
Input: arr = [2, 4, 4, 4, 6], x = 4 → Output: 1
Input: arr = [1, 1, 1, 2, 3], x = 1 → Output: 0
Input: arr = [5, 6, 7], x = 8 → Output: -1 
def first_occurrence_bs(arr, x):
    low, high, result = 0, len(arr)-1, -1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] == x:
            result = mid
            high = mid - 1
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return result
Modified binary search: move left if found. Time Complexity: O(log n).

10. Find last occurrence using Binary Search

Examples:
Input: arr = [2, 4, 4, 4, 6], x = 4 → Output: 3
Input: arr = [1, 1, 1, 2, 3], x = 1 → Output: 2
Input: arr = [5, 6, 7], x = 10 → Output: -1 
def last_occurrence_bs(arr, x):
    low, high, result = 0, len(arr)-1, -1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] == x:
            result = mid
            low = mid + 1
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return result
Modified binary search: move right if found. Time Complexity: O(log n).
© 2025 Learning Sutras | Champak Roy