Searching Algorithms and Big O Notation

Programming 1 vs. Programming 2/3: Programming 1 focuses on fundamental concepts, while Programming 2 and, to a greater extent, Programming 3, delve into algorithms and more intricate programming concepts. Much of it becomes a "show and tell" of Python's capabilities.
Class Progress: The class is at its midpoint, with students performing well.

Definition: An algorithm that iterates over all elements in an array (or list) to check if the current element matches a target element.
Process:
- Starts at the beginning of the list (element at index $0$ ).
- Compares each element sequentially with the target element.
- If a match is found, it returns the index of the current element.
- If no element equals the target element after checking the entire list, it returns $-1$ (indicating the element was not found).
Analogy: Counting through a list from start to finish to find a specific value.
Example: Searching for 30 in [10, 50, 30, 70, 80, 20, 90, 40].
- Compares 30 with 10 (no).
- Compares 30 with 50 (no).
- Compares 30 with 30 (yes) - stops and returns the index.
**Python Code Example (linear_search.py):
- A search function takes an array, its length ( $n$ ), and the target element ( $x$ ).
- It uses a for loop for i in range(0, n) to iterate.
- if arr[i] == x: returns i (the index).
- If the loop completes without finding x, it returns $-1$ .
- Driver Code: Creates an array (e.g., [2, 3, 4, 10, 40]), defines x (e.g., 10), calculates n = len(array), calls the search function, and prints the result, indicating if the element was found and at what index.

Purpose: Used to determine the complexity of algorithms, particularly how their runtime or space requirements grow as the input size increases.
Basic Examples:
- $O(1) ext{ (Constant Time)}:$ The algorithm takes a constant amount of time, regardless of the input size. Example: Accessing an element directly, or a single line of code execution. Best-case scenario for searching at the first element.
- $O(n) ext{ (Linear Time)}:$ The algorithm's runtime grows linearly with the input size ( $n$ ). If there are $n$ elements, it might perform $n$ operations. Example: A single loop that iterates through all elements. $n$ is a placeholder for an unknown number of iterations that depends on the input size.
- $O(n^2) ext{ (Quadratic Time)}:$ The algorithm's runtime grows proportionally to the square of the input size. Example: A nested loop (a loop inside another loop), commonly seen in matrix operations.
Best Algorithms: Algorithms with $n$ as small as possible (e.g., $O(1)$ or $O( ext{log } n)$ ) are considered the most efficient, though they might be more complex and potentially use more memory.

Best Case: $O(1)$ - when the target element is the first element in the list.
Worst Case: $O(n)$ - when the target element is the last element or not present in the list, requiring a scan of all $n$ elements.
Average Case: Approximately $O(n)$ - on average, it will need to check about half the elements, which is still considered linear for Big O purposes.
Applications, Advantages, Disadvantages, When to Use It: (Details left for personal study from external resources mentioned in the transcript).

Definition: A search algorithm used to find the position of a target value within a sorted array (or list).
Prerequisite: The data structure must be sorted. Accessing any element must take constant time ( $O(1)$ ).
Process (Iterative Logic):
1. Find the Middle: Compare the target element with the middle value of the current search interval.
2. Halve the Interval:
  - If the middle value equals the target, the search is complete.
  - If the middle value is less than the target, discard the left half of the interval (including the middle element) and continue searching in the right half.
  - If the middle value is greater than the target, discard the right half of the interval (including the middle element) and continue searching in the left half.
3. Repeat: Continuously divide the search interval in half until the target is found or the interval becomes empty.
Example: Finding 7 in [1, 2, 3, 4, 5, 6, 7, 8, 9].
1. Middle is 5. 7 > 5, so discard [1, 2, 3, 4, 5]. New interval: [6, 7, 8, 9].
2. Middle of [6, 7, 8, 9] is 7 (or 8 depending on rounding, for simplicity let's say 7). If 7 is chosen, 7 = 7, so target found.
Versions: Iterative and Recursive.

Function Signature: binary_search(arr, low, high, x)
- arr: The sorted array.
- low: The starting index of the search interval (initially $0$ ).
- high: The ending index of the search interval (initially len(arr) - 1).
- x: The target element.
Algorithm:
- while low <= high: loop continues as long as the search interval is valid.
- mid = low + (high - low) // 2: Calculates the middle index. Using integer division // to ensure an integer index. (The formula (low + high) // 2 also works, but low + (high - low) // 2 is safer to prevent integer overflow with very large low and high values in some languages).
- if arr[mid] == x:: If target found, return mid.
- elif arr[mid] < x:: If target is in the right half, update low = mid + 1.
- else: (meaning arr[mid] > x): If target is in the left half, update high = mid - 1.
- return -1: If the loop finishes (meaning low > high), the element was not found.
Performance: For small datasets, its speed difference with linear search might not be visually apparent, but for large datasets (millions of elements), binary search is significantly faster.

Function Signature: binary_search_recursive(arr, low, high, x) (similar parameters).
Algorithm:
- Base Case: if high >= low: (if the interval is valid, proceed).
- Calculate mid similar to the iterative version.
- if arr[mid] == x:: Returns mid.
- elif arr[mid] > x:: Recursively calls binary_search_recursive(arr, low, mid - 1, x) (search left half).
- else: (meaning arr[mid] < x): Recursively calls binary_search_recursive(arr, mid + 1, high, x) (search right half).
- else: (if high < low, i.e., base case is False): Returns $-1$ . The function calls then