Learning

Searching Algorithms

Linear Search

python

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

print(linear_search([5, 3, 8, 1, 9], 8))  # 2

Binary Search (Iterative)

python

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

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

Binary Search (Recursive)

python

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

Binary Search Variants

python

# Lower bound: first index >= target
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

# Upper bound: first index > target
def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

arr = [1, 2, 4, 4, 4, 6, 7]
print(lower_bound(arr, 4))  # 2 (first 4)
print(upper_bound(arr, 4))  # 5 (first > 4)
print(f'Count of 4s: {upper_bound(arr, 4) - lower_bound(arr, 4)}')  # 3

Search in Rotated Sorted Array

python

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[left] <= arr[mid]:  # Left half is sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half is sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

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

Jump Search

python

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    for i in range(prev, min(step, n)):
        if arr[i] == target:
            return i
    return -1

Interpolation Search

python

def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right and arr[left] <= target <= arr[right]:
        if left == right:
            return left if arr[left] == target else -1
        pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])
        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    return -1

Key Rules

•Linear search: O(n) — only option for unsorted data, but simple and no preprocessing needed
•Binary search: O(log n) — REQUIRES sorted array; uses divide-and-conquer halving
•Use `left + (right - left) // 2` instead of `(left + right) // 2` to avoid integer overflow
•Lower bound = first index where arr[i] >= target; Upper bound = first index where arr[i] > target
•Rotated array binary search: determine which half is sorted, then check if target is in that half
•Jump search: O(√n) — jump by √n steps then linear search backwards; better than linear, worse than binary

Your Task

Implement: 1) `linear_search(arr, target)`. 2) `binary_search(arr, target)` iterative. 3) `binary_search_rec(arr, target)` recursive. 4) `lower_bound(arr, target)` and `upper_bound(arr, target)`. 5) `search_rotated(arr, target)`. 6) `count_occurrences(arr, target)` using lower/upper bound. Demonstrate all with clear test cases showing return values.

Learning

Searching Algorithms

Linear Search

python

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

print(linear_search([5, 3, 8, 1, 9], 8))  # 2

Binary Search (Iterative)

python

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

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

Binary Search (Recursive)

python

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

Binary Search Variants

python

# Lower bound: first index >= target
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

# Upper bound: first index > target
def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

arr = [1, 2, 4, 4, 4, 6, 7]
print(lower_bound(arr, 4))  # 2 (first 4)
print(upper_bound(arr, 4))  # 5 (first > 4)
print(f'Count of 4s: {upper_bound(arr, 4) - lower_bound(arr, 4)}')  # 3

Search in Rotated Sorted Array

python

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[left] <= arr[mid]:  # Left half is sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half is sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

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

Jump Search

python

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    for i in range(prev, min(step, n)):
        if arr[i] == target:
            return i
    return -1

Interpolation Search

python

def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right and arr[left] <= target <= arr[right]:
        if left == right:
            return left if arr[left] == target else -1
        pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])
        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    return -1

Key Rules

•Linear search: O(n) — only option for unsorted data, but simple and no preprocessing needed
•Binary search: O(log n) — REQUIRES sorted array; uses divide-and-conquer halving
•Use `left + (right - left) // 2` instead of `(left + right) // 2` to avoid integer overflow
•Lower bound = first index where arr[i] >= target; Upper bound = first index where arr[i] > target
•Rotated array binary search: determine which half is sorted, then check if target is in that half
•Jump search: O(√n) — jump by √n steps then linear search backwards; better than linear, worse than binary

Your Task