Searching Algo

Let’s dive into some of the most common searching algorithms, their pseudocode, and their time/space complexities:

---

1. Linear Search

Linear Search sequentially checks each element in the array until the target element is found or the end of the array is reached.

Pseudocode:

javaCopy codeLinearSearch(arr, target):
    for i = 0 to length(arr)-1:
        if arr[i] == target:
            return i
    return -1  // target not found

Time Complexity:

• Best Case: O(1) (when the target is the first element)

• Average Case: O(n)

• Worst Case: O(n) (when the target is the last element or not present)

Space Complexity:

• O(1) (In-place search)

---

2. Binary Search

Binary Search works on sorted arrays. It repeatedly divides the search interval in half. If the target value is smaller than the middle value, the search continues in the lower half, otherwise, it continues in the upper half.

Pseudocode (Recursive Version):

vbnetCopy codeBinarySearch(arr, target, low, high):
    if low > high:
        return -1  // target not found
    mid = (low + high) / 2
    if arr[mid] == target:
        return mid
    else if arr[mid] > target:
        return BinarySearch(arr, target, low, mid - 1)
    else:
        return BinarySearch(arr, target, mid + 1, high)

Time Complexity:

• Best Case: O(1) (when the middle element is the target)

• Average Case: O(log n)

• Worst Case: O(log n)

Space Complexity:

• O(log n) for recursive version (due to recursive call stack)

• O(1) for iterative version

The iterative version of Binary Search is space-efficient because it avoids the function call stack that the recursive version uses. This ensures a space complexity of O(1).

Here's how the iterative binary search works:

---

Iterative Binary Search Pseudocode

kotlinCopy codeIterativeBinarySearch(arr, target):
    low = 0
    high = length(arr) - 1

    while low <= high:
        mid = low + (high - low) / 2  // Find the middle element

        if arr[mid] == target:
            return mid  // Target found at mid
        elif arr[mid] < target:
            low = mid + 1  // Search the right half
        else:
            high = mid - 1  // Search the left half

    return -1  // Target not found

---

Explanation:

1. Initialization: We initialize two pointers, low and high, to represent the current search boundaries in the sorted array.

   • low = 0 (the start of the array).

   • high = length(arr) - 1 (the end of the array).

2. Loop: We repeatedly search within the bounds low and high until the range becomes invalid (i.e., low > high), indicating that the target element is not present.

3. Finding the Middle Element:

   • We calculate the index of the middle element using mid = low + (high - low) / 2.

   • This formula is preferred over (low + high) / 2 to avoid potential integer overflow.

4. Comparison:

   • If arr[mid] is the target, return the index mid.

   • If the target is smaller than arr[mid], adjust the search range to the left half by updating high = mid - 1.

   • If the target is larger than arr[mid], adjust the search range to the right half by updating low = mid + 1.

5. Termination: The loop continues until low > high, at which point the search space has been exhausted, and the target is not found.

6. Space Efficiency: Since this version uses only a few extra variables (low, high, mid), the space complexity is O(1).

---

Time Complexity:

• Best Case: O(1) (if the target is found in the middle of the array on the first iteration).

• Worst and Average Case: O(log n) (since with each iteration, the search space is halved).

Space Complexity:

• O(1): No recursion is used, and only a constant amount of extra space is needed for variables like low, high, and mid.

---

Example Walkthrough:

Consider the sorted array arr = [1, 3, 5, 7, 9, 11, 13, 15], and the target is 9.

1. low = 0, high = 7, mid = 3.

   • arr[3] = 7, which is less than 9. So, adjust low = mid + 1 = 4.

2. low = 4, high = 7, mid = 5.

   • arr[5] = 11, which is greater than 9. So, adjust high = mid - 1 = 4.

3. low = 4, high = 4, mid = 4.

   • arr[4] = 9, which is equal to the target. Return 4.

---

3. Jump Search

Jump Search is also designed for sorted arrays. The idea is to jump ahead by fixed steps (block size), and when the block where the target might be located is found, a linear search within the block is performed.

Pseudocode:

arduinoCopy codeJumpSearch(arr, target):
    n = length(arr)
    step = sqrt(n)
    prev = 0
    while arr[min(step, n)-1] < target:
        prev = step
        step += sqrt(n)
        if prev >= n:
            return -1  // target not found
    for i = prev to min(step, n)-1:
        if arr[i] == target:
            return i
    return -1  // target not found

Time Complexity:

• Best Case: O(1)

• Average Case: O(√n)

• Worst Case: O(√n)

Space Complexity:

• O(1) (In-place search)

---

4. Interpolation Search

Interpolation Search is an improved variant of binary search for uniformly distributed data. Instead of dividing the array in half, it estimates the position of the target based on the values of the elements.

Pseudocode:

perlCopy codeInterpolationSearch(arr, target, low, high):
    while low <= high and target >= arr[low] and target <= arr[high]:
        pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1  // target not found

Time Complexity:

• Best Case: O(1)

• Average Case: O(log log n)

• Worst Case: O(n) (if the elements are not uniformly distributed)

Space Complexity:

• O(1) (In-place search)

---

5. Exponential Search

Exponential Search is used to search for an element in a sorted array. It works by increasing the search range exponentially, followed by a binary search in the found range.

Pseudocode:

lessCopy codeExponentialSearch(arr, target):
    if arr[0] == target:
        return 0
    i = 1
    while i < length(arr) and arr[i] <= target:
        i = i * 2
    return BinarySearch(arr, target, i/2, min(i, length(arr)-1))

Time Complexity:

• Best Case: O(1)

• Average Case: O(log n)

• Worst Case: O(log n)

Space Complexity:

• O(log n) for binary search recursive version

• O(1) for binary search iterative version

---

6. Fibonacci Search

Fibonacci Search works on sorted arrays and uses a Fibonacci sequence to divide the array. The idea is to eliminate large chunks of the array using Fibonacci numbers and reduce the search space.

Pseudocode:

javaCopy codeFibonacciSearch(arr, target):
    n = length(arr)
    fibMMm2 = 0  // (m-2)'th Fibonacci number
    fibMMm1 = 1  // (m-1)'th Fibonacci number
    fibM = fibMMm2 + fibMMm1  // m'th Fibonacci number
    while fibM < n:
        fibMMm2 = fibMMm1
        fibMMm1 = fibM
        fibM = fibMMm2 + fibMMm1
    offset = -1
    while fibM > 1:
        i = min(offset + fibMMm2, n-1)
        if arr[i] < target:
            fibM = fibMMm1
            fibMMm1 = fibMMm2
            fibMMm2 = fibM - fibMMm1
            offset = i
        else if arr[i] > target:
            fibM = fibMMm2
            fibMMm1 = fibMMm1 - fibMMm2
            fibMMm2 = fibM - fibMMm1
        else:
            return i
    if fibMMm1 and arr[offset+1] == target:
        return offset+1
    return -1  // target not found

Time Complexity:

• Best Case: O(1)

• Average Case: O(log n)

• Worst Case: O(log n)

Space Complexity:

• O(1) (In-place search)

---

7. Ternary Search

Ternary Search is a divide-and-conquer algorithm similar to binary search, but it divides the array into three parts and recursively searches in the relevant part.

Pseudocode:

kotlinCopy codeTernarySearch(arr, low, high, target):
    if high >= low:
        mid1 = low + (high - low) / 3
        mid2 = high - (high - low) / 3
        if arr[mid1] == target:
            return mid1
        if arr[mid2] == target:
            return mid2
        if target < arr[mid1]:
            return TernarySearch(arr, low, mid1 - 1, target)
        if target > arr[mid2]:
            return TernarySearch(arr, mid2 + 1, high, target)
        return TernarySearch(arr, mid1 + 1, mid2 - 1, target)
    return -1  // target not found

Time Complexity:

• Best Case: O(1)

• Average Case: O(log n)

• Worst Case: O(log n)

Space Complexity:

• O(log n) for recursive version (due to recursive call stack)

• O(1) for iterative version

---

8. Depth-First Search (DFS) (for graph/tree data structures)

DFS explores as far as possible along each branch before backtracking. It uses a stack (either explicitly or via recursion) to track the current path.

Pseudocode (for a graph):

sqlCopy codeDFS(graph, start):
    create a stack S
    push start onto S
    mark start as visited
    while S is not empty:
        node = S.pop()
        for each neighbor of node:
            if neighbor is not visited:
                push neighbor onto S
                mark neighbor as visited

Time Complexity:

• Best Case: O(V + E) (where V is the number of vertices and E is the number of edges)

• Average Case: O(V + E)

• Worst Case: O(V + E)

Space Complexity:

• O(V) (due to recursion or stack space)

---

9. Breadth-First Search (BFS) (for graph/tree data structures)

BFS explores all nodes at the present depth before moving on to the nodes at the next depth level. It uses a queue to track the next node to explore.

Pseudocode (for a graph):

lessCopy codeBFS(graph, start):
    create a queue Q
    enqueue start onto Q
    mark start as visited
    while Q is not empty:
        node = Q.dequeue()
        for each neighbor of node:
            if neighbor is not visited:
                enqueue neighbor onto Q
                mark neighbor as visited

Time Complexity:

• Best Case: O(V + E)

• Average Case: O(V + E)

• Worst Case: O(V + E)

Space Complexity:

• O(V) (due to the queue space)