Master 10 essential array problems on searching & sorting with Python. Includes examples, explanations, and complexities for interviews & learning.

Array Searching & Sorting – Assignments 11 to 20 (with Python Solutions, Examples & Complexity)

11. Count occurrences of an element in a sorted array

Examples:
arr = [1, 2, 2, 2, 3], x = 2 → Output: 3
arr = [5, 5, 5, 5], x = 5 → Output: 4
arr = [10, 20, 30], x = 25 → Output: 0

def count_occurrences(arr, x):
    def first(arr, x):
        low, high, res = 0, len(arr)-1, -1
        while low <= high:
            mid = (low+high)//2
            if arr[mid] == x:
                res, high = mid, mid-1
            elif arr[mid] < x:
                low = mid+1
            else:
                high = mid-1
        return res
    def last(arr, x):
        low, high, res = 0, len(arr)-1, -1
        while low <= high:
            mid = (low+high)//2
            if arr[mid] == x:
                res, low = mid, mid+1
            elif arr[mid] < x:
                low = mid+1
            else:
                high = mid-1
        return res
    f, l = first(arr, x), last(arr, x)
    return 0 if f == -1 else l-f+1

print(count_occurrences([1,2,2,2,3], 2))  # 3
      

Use modified binary search to find first and last occurrence, then subtract. Time Complexity: O(log n) Space Complexity: O(1)

12. Search in a rotated sorted array

Examples:
arr = [4,5,6,7,0,1,2], x = 0 → Output: 4
arr = [4,5,6,7,0,1,2], x = 3 → Output: -1
arr = [1], x = 1 → Output: 0

def search_rotated(arr, x):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] == x:
            return mid
        if arr[low] <= arr[mid]:
            if arr[low] <= x < arr[mid]:
                high = mid-1
            else:
                low = mid+1
        else:
            if arr[mid] < x <= arr[high]:
                low = mid+1
            else:
                high = mid-1
    return -1

print(search_rotated([4,5,6,7,0,1,2], 0))  # 4
      

Use modified binary search with pivot condition. Time Complexity: O(log n) Space Complexity: O(1)

13. Find minimum element in a rotated sorted array

Examples:
arr = [4,5,6,7,0,1,2] → Output: 0
arr = [3,4,5,1,2] → Output: 1
arr = [1,2,3,4] → Output: 1

def find_min_rotated(arr):
    low, high = 0, len(arr)-1
    while low < high:
        mid = (low+high)//2
        if arr[mid] > arr[high]:
            low = mid+1
        else:
            high = mid
    return arr[low]

print(find_min_rotated([4,5,6,7,0,1,2]))  # 0
      

Compare middle with high to decide which half to go. Time Complexity: O(log n) Space Complexity: O(1)

14. Square root of a number using Binary Search

Examples:
n = 16 → Output: 4
n = 8 → Output: 2 (floor value)
n = 1 → Output: 1

def sqrt_binary(n):
    low, high, ans = 0, n, 0
    while low <= high:
        mid = (low+high)//2
        if mid*mid == n:
            return mid
        elif mid*mid < n:
            ans = mid
            low = mid+1
        else:
            high = mid-1
    return ans

print(sqrt_binary(8))  # 2
      

Binary search between 0..n for integer square root. Time Complexity: O(log n) Space Complexity: O(1)

15. Find peak element

Examples:
arr = [1,2,3,1] → Output: 2 (index of 3)
arr = [1,2,1,3,5,6,4] → Output: 5 (index of 6)
arr = [10,20,15] → Output: 1

def find_peak(arr):
    low, high = 0, len(arr)-1
    while low < high:
        mid = (low+high)//2
        if arr[mid] < arr[mid+1]:
            low = mid+1
        else:
            high = mid
    return low

print(find_peak([1,2,3,1]))  # 2
      

Use binary search approach to find any peak. Time Complexity: O(log n) Space Complexity: O(1)

16. Find element in a bitonic array

A bitonic array is a sequence of numbers that is first strictly increasing and then strictly decreasing. This means that the elements ascend to a peak value and then descend

Examples:
arr = [1,3,8,12,4,2], x = 4 → Output: 4
arr = [1,3,8,12,4,2], x = 12 → Output: 3
arr = [1,3,8,12,4,2], x = 7 → Output: -1

def search_bitonic(arr, x):
    def peak(arr):
        low, high = 0, len(arr)-1
        while low < high:
            mid = (low+high)//2
            if arr[mid] < arr[mid+1]:
                low = mid+1
            else:
                high = mid
        return low
    def bin_search(arr, low, high, x, asc=True):
        while low <= high:
            mid = (low+high)//2
            if arr[mid] == x:
                return mid
            if asc:
                if arr[mid] < x: low = mid+1
                else: high = mid-1
            else:
                if arr[mid] > x: low = mid+1
                else: high = mid-1
        return -1
    p = peak(arr)
    idx = bin_search(arr, 0, p, x, True)
    return idx if idx != -1 else bin_search(arr, p+1, len(arr)-1, x, False)

print(search_bitonic([1,3,8,12,4,2], 4))  # 4
      

First find peak, then binary search in increasing and decreasing halves. Time Complexity: O(log n) Space Complexity: O(1)

17. Bubble Sort

Examples:
arr = [5,1,4,2,8] → Output: [1,2,4,5,8]
arr = [3,2,1] → Output: [1,2,3]
arr = [1,2,3] → Output: [1,2,3]

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

print(bubble_sort([5,1,4,2,8]))  # [1,2,4,5,8]
      

Repeatedly swap adjacent elements if out of order. Time Complexity: O(n²) Space Complexity: O(1)

18. Optimized Bubble Sort

Examples:
arr = [1,2,3] → Output: [1,2,3]
arr = [3,2,1] → Output: [1,2,3]
arr = [2,1,3] → Output: [1,2,3]

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped: break
    return arr

print(bubble_sort_optimized([1,2,3]))  # [1,2,3]
      

Stops early if no swaps happened in a pass. Best Case: O(n) Worst Case: O(n²) Space Complexity: O(1)

19. Selection Sort

Examples:
arr = [64,25,12,22,11] → Output: [11,12,22,25,64]
arr = [3,2,1] → Output: [1,2,3]
arr = [1,2,3] → Output: [1,2,3]

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(selection_sort([64,25,12,22,11]))  # [11,12,22,25,64]

      

Select minimum in each pass and swap. Time Complexity: O(n²) Space Complexity: O(1)

20. Insertion Sort

Examples:
arr = [12,11,13,5,6] → Output: [5,6,11,12,13]
arr = [3,2,1] → Output: [1,2,3]
arr = [1,2,3] → Output: [1,2,3]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

print(insertion_sort([12,11,13,5,6]))  # [5,6,11,12,13]
      

Each element is inserted in its correct position within the sorted part of array. Best Case: O(n) (already sorted) Worst Case: O(n²) (reverse order) Space Complexity: O(1)

© 2025 Learning Sutras | Champak Roy