Introduction to Searching

Searching is the process of finding a particular element in a collection of items, such as an array, list, or database. The goal of searching is to locate the position of the desired item in the collection, if it exists, or to determine that the item is not present.

Searching is one of the most fundamental operations in computer science. It is used extensively in many applications where data retrieval is required, such as:

1. Databases: Finding a record based on a key (e.g., retrieving customer information using an ID).

2. File Systems: Locating a file by its name or metadata.

3. Web Search Engines: Searching for relevant information from vast data repositories.

4. Algorithms: As part of many algorithms that require efficient data lookup, such as sorting algorithms or graph traversal.

Efficient searching techniques reduce the time it takes to find elements, which is crucial for performance, especially in large datasets. Different search algorithms, such as linear and binary search, are optimized for different kinds of data structures and applications.

Linear Search

Linear Search is the simplest searching algorithm. It works by sequentially checking each element in an array until the desired element is found or the entire array is traversed. Linear Search is particularly useful for small or unsorted datasets, where other more complex algorithms may not be as effective or necessary.

The Linear Search algorithm starts from the first element of the array and compares it with the target value (the element we are searching for). If it matches, the search stops, and the index of the element is returned. If it doesn't match, the algorithm continues checking the next element. If the algorithm reaches the end of the array without finding the target element, it returns a failure indication, such as -1.

Steps for Linear Search:

1. Start at the first element of the array.

2. Compare the current element with the target value.

3. If the current element matches the target value, return the index.

4. If it does not match, move to the next element.

5. Repeat steps 2-4 until the target value is found or the end of the array is reached.

6. If the target value is not found after scanning all elements, return a failure signal (e.g., -1).

Example of Linear Search in an Array

Suppose we have an array:

arr = [34, 78, 12, 90, 54, 67]

and we are searching for the target value 90.

1. Start at the first element: 34. Does 34 == 90? No.

2. Move to the next element: 78. Does 78 == 90? No.

3. Move to the next element: 12. Does 12 == 90? No.

4. Move to the next element: 90. Does 90 == 90? Yes.

5. The target element 90 is found at index 3. Return the index 3.

If the target value was not in the array, the algorithm would continue until it had checked all elements and returned a failure result (like -1).

C Code for Linear Search

#include <stdio.h>

// Function for linear search
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // Return the index if the target is found
        }
    }
    return -1;  // Return -1 if the target is not found
}

int main() {
    int arr[] = {34, 78, 12, 90, 54, 67};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 90;

    int result = linearSearch(arr, n, target);

    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found in the array\n");
    }

    return 0;
}

Explanation of the C Code

• linearSearch function: This function takes an array (arr[]), its size (n), and the target value (target) as inputs. It iterates over the array and compares each element with the target value. If a match is found, it returns the index of the element. If no match is found, it returns -1.

• main function: The program initializes an array of integers and calls the linearSearch function to find a specific target element. It then prints the index where the target is found or indicates that the element is not present.

Time Complexity of Linear Search

Worst-Case Time Complexity: \( O(n) \)

In the worst-case scenario, the target element may be located at the very last position of the array, or it may not be present in the array at all. In both cases, Linear Search must check all \(n\) elements, resulting in a time complexity of \(O(n)\).

Best-Case Time Complexity: \( O(1) \)

In the best-case scenario, the target element is located at the first position of the array. Linear Search only needs to make one comparison to find the target, resulting in a time complexity of \(O(1)\).

Average-Case Time Complexity: \( O(n) \)

On average, the target element is likely to be located somewhere in the middle of the array. Linear Search will typically need to check about half of the array's elements before finding the target. The average time complexity is still \(O(n)\) since, on average, it checks \(n/2\) elements, but the constants are ignored in Big-O notation.

Space Complexity

The space complexity of Linear Search is \(O(1)\), as it only requires a constant amount of extra memory (a few variables for iteration and comparison).

Binary Search

Binary Search is an efficient algorithm for finding a target element in a sorted array. Unlike linear search, which scans each element one by one, binary search repeatedly divides the search interval in half. If the target element is less than the middle element, the search continues on the left half; otherwise, it continues on the right half. Binary Search is much faster than linear search, with a time complexity of O(log n).

How Binary Search Works

1. Start with the entire sorted array.

2. Compare the target element with the middle element of the array.

3. If the target is equal to the middle element, the search is successful, and the index is returned.

4. If the target is smaller than the middle element, recursively search the left half.

5. If the target is larger than the middle element, recursively search the right half.

6. Repeat the process until the element is found or the search interval is empty.

Example of Binary Search in an Array

Suppose we have a sorted array:

arr = [10, 22, 35, 47, 53, 62, 75, 88, 96]

and we are searching for the target value 53.

1. Start with the whole array: arr[0] to arr[8].

2. The middle element is at index 4: arr[4] = 53. Since this matches the target, return the index 4.

C Code for Binary Search in an Array

#include <stdio.h>

// Iterative Binary Search function
int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if target is present at mid
        if (arr[mid] == target) {
            return mid;
        }
        // If target is greater, ignore the left half
        if (arr[mid] < target) {
            low = mid + 1;
        }
        // If target is smaller, ignore the right half
        else {
            high = mid - 1;
        }
    }
    // If the element is not present, return -1
    return -1;
}

int main() {
    int arr[] = {10, 22, 35, 47, 53, 62, 75, 88, 96};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 53;

    int result = binarySearch(arr, n, target);

    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found in the array\n");
    }

    return 0;
}

Binary Search on a Binary Search Tree (BST)

Binary Search can also be applied to Binary Search Trees (BST). A BST is a binary tree where the left child contains values smaller than the parent, and the right child contains values larger than the parent. Binary Search on a BST works similarly to searching in a sorted array: traverse left if the target is smaller than the current node, and traverse right if it is larger.

C Code for Binary Search on a BST

#include <stdio.h>
#include <stdlib.h>

// Definition of a binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Binary Search on a Binary Search Tree (recursive)
struct Node* searchBST(struct Node* root, int target) {
    // Base case: root is null or target is present at root
    if (root == NULL || root->data == target) {
        return root;
    }

    // Target is greater than root's key, search the right subtree
    if (target > root->data) {
        return searchBST(root->right, target);
    }

    // Target is smaller than root's key, search the left subtree
    return searchBST(root->left, target);
}

int main() {
    // Manually create a binary search tree
    struct Node* root = newNode(50);
    root->left = newNode(30);
    root->right = newNode(70);
    root->left->left = newNode(20);
    root->left->right = newNode(40);
    root->right->left = newNode(60);
    root->right->right = newNode(80);

    int target = 40;

    struct Node* result = searchBST(root, target);

    if (result != NULL) {
        printf("Element %d found in the BST\n", result->data);
    } else {
        printf("Element not found in the BST\n");
    }

    return 0;
}

Time Complexity of Binary Search

Array (Iterative or Recursive Binary Search)

• Worst-case Time Complexity: \(O(\log n)\)

  • Each time, Binary Search reduces the search space by half. In the worst case, the algorithm will make \( \log_2 n \) comparisons before it finds the target or concludes the target isn't in the array.

• Best-case Time Complexity: \(O(1)\)

  • The best case occurs when the middle element is the target value during the first comparison.

Binary Search Tree (BST)

• Worst-case Time Complexity: \(O(h)\) where \(h\) is the height of the tree.

  • In the worst case, the tree is skewed, and the height of the tree is \(n\), making the time complexity \(O(n)\).

• Best-case Time Complexity: \(O(1)\)

  • The best case occurs when the root node contains the target value.

Space Complexity

• For the iterative binary search in an array, the space complexity is \(O(1)\) since no additional memory is required apart from a few variables.

• For the recursive binary search, the space complexity is \(O(\log n)\) due to the recursive stack calls.

• For a BST, the space complexity is \(O(h)\), where \(h\) is the height of the tree, and recursion consumes memory proportional to the height.