Sequential, Binary and Tree search

Sequential Search

Sequential search, also known as linear search, is a simple searching algorithm used to find a specific target value within a collection of elements, such as an array or a list. The search starts at the beginning of the collection and checks each element one by one until the target value is found or until the end of the collection is reached.

Algorithm for Sequential search

ALGORITHM SequentialSearch2(A[0..n], K)
// Implements sequential search with a search key as a sentinel
// Input: An array A of n elements and a search key K
// Output: The index of the first element in A[0..n − 1] whose value is equal to K or −1 if no such element is found

A[n] ← K // Set the last element of the array as the search key
i ← 0 // Initialize the index to start searching from

while A[i] ≠ K do // Continue searching until the search key is found
    i ← i + 1 // Move to the next element

if i < n then // If the index is within the bounds of the array
    return i // Return the index where the search key is found
else
    return −1 // Return -1 indicating the search key is not found in the array

Write a C++ program to implement Linear Search

#include <iostream>

using namespace std;

int linearSearch(int arr[], int size, int key) {
    for (int i = 0; i < size; ++i) {
        if (arr[i] == key) {
            return i; // Return the index where the key is found
        }
    }
    return -1; // Return -1 if the key is not found
}

int main() {
    int arr[] = {4, 2, 8, 1, 5, 9, 3};
    int size = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array
    int key = 5;
    
    int index = linearSearch(arr, size, key);
    
    if (index != -1) {
        cout << "Element found at index " << index << endl;
    } else {
        cout << "Element not found" << endl;
    }
    
    return 0;
}

Linear Search Example: search key = 4 in the given list of numbers:

Binary Search

Binary search is a fundamental algorithm used to locate a specific element within a sorted array or list efficiently. It works by repeatedly dividing the search interval in half until the target element is found or the search interval is empty.

Properties of Binary Search

Time Complexity: Binary search has a time complexity of O(log n), making it highly efficient for searching large datasets due to its logarithmic time complexity.

Divide and Conquer Approach: Binary search employs a divide and conquer strategy, continually halving the search interval until the target element is found or the search space is empty, ensuring efficient reduction of the search space with each iteration.

Requirement of Sorted Data: Binary search necessitates the data to be sorted, either in ascending or descending order, as it relies on comparing the target value with the middle element, a fundamental aspect for correct functionality.

Algorithm for Binary Search

function BINARY_SEARCH(A, lower_bound, upper_bound, VAL):
    BEG = lower_bound
    END = upper_bound
    POS = -1
    
    while BEG <= END:
        MID = (BEG + END) / 2
        
        if A[MID] == VAL:
            POS = MID
            return POS
        
        elif A[MID] > VAL:
            END = MID - 1
            
        else:
            BEG = MID + 1
    
    if POS == -1:
        print("VALUE IS NOT PRESENT IN THE ARRAY")

Algorithm for Binary Search using recursion

function binary_search_recursive(A, lower_bound, upper_bound, VAL):
    if lower_bound > upper_bound:
        return -1
    
    mid = (lower_bound + upper_bound) // 2
    
    if A[mid] == VAL:
        return mid
    
    elif A[mid] > VAL:
        return binary_search_recursive(A, lower_bound, mid - 1, VAL)
    
    else:
        return binary_search_recursive(A, mid + 1, upper_bound, VAL)

Write a C++ program to implement Binary Search using recursion.

#include <iostream>

using namespace std;

int binarySearch(int arr[], int size, int key) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == key) {
            return mid;
        }

        if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 5;

    int result = binarySearch(arr, size, key);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Binary Search Example: search key = 10

Tree Search

 Please follow  Tree search