The Searching Algorithms - From Linear to Binary and Beyond

Introduction

When it comes to searching for something, whether it be a needle in a haystack or that one specific file on your computer, it can often feel like an impossible task. But fear not, for there are a variety of searching algorithms at our disposal to make the process a breeze. In this article, we’ll take a closer look at some of the most popular and efficient searching algorithms, complete with pseudocode and C# examples to help you put them into practice.

Linear Search

The most basic searching algorithm is the linear search. As the name suggests, it involves going through each element in a list one by one until the desired item is found. It’s not the most efficient algorithm out there, but it’s a great starting point for understanding the concept of searching.

Pseudocode for the linear search algorithm:

function linear_search(list, item)
    for i = 0 to list.length-1
        if list[i] == item
            return i
    return -1

Coding example in C#:

int LinearSearch(int[] list, int item) {
    for (int i = 0; i < list.Length; i++) {
        if (list[i] == item) {
            return i;
        }
    }
    return -1;
}

Binary Search

Binary search is a much more efficient algorithm than linear search, but it can only be used on sorted lists. The idea is to start in the middle of the list and compare the item we’re searching for with the middle element. If it’s a match, we’re done. If it’s less than the middle element, we know the item must be in the left half of the list. If it’s greater, the item must be in the right half. We then repeat this process on the appropriate half until we find the item or determine that it’s not in the list. Binary Search algorithms pseudocode

function binary_search(list, item)
    low = 0
    high = list.length-1
    while low <= high
        mid = (low + high) / 2
        if list[mid] == item
            return mid
        else if list[mid] > item
            high = mid - 1
        else
            low = mid + 1
    return -1

C# Coding example:

int BinarySearch(int[] list, int item) {
    int low = 0;
    int high = list.Length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (list[mid] == item) {
            return mid;
        }
        else if (list[mid] > item) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return -1;
}

Jump Search

Jump search is an algorithm that is particularly useful for large lists with a small number of elements. It’s a combination of linear search and binary search. First, we jump a certain number of elements at a time (the “jump size”) until we find an element that is greater than or equal to the item we’re searching for. Then, we perform a linear search on the sublist starting from the last element we landed on.

Jump Search algorithm pseudocode:

function jump_search(list, item)
    jump_size = sqrt(list.length)
    start = 0
    end = jump_size
    while end < list.length
        if list[end] >= item
            break
        start = end
        end += jump_size
    for i = start to min(end, list.length-1)
        if list[i] == item
            return i
    return -1

C# Coding examples:

int JumpSearch(int[] list, int item) {
    int jumpSize = (int)Math.Sqrt(list.Length);
    int start = 0;
    int end = jumpSize;
    while (end < list.Length) {
        if (list[end] >= item) {
            break;
        }
        start = end;
        end += jumpSize;
    }
    for (int i = start; i <= Math.Min(end, list.Length - 1); i++) {
        if (list[i] == item) {
            return i;
        }
    }
    return -1;
}

Ternary Search

Ternary search is a divide-and-conquer algorithm similar to binary search, but with three division points rather than two. It’s useful for finding the minimum or maximum value in a unimodal function (a function that increases and then decreases, or vice versa). Algorithms pseudocode:

function ternary_search(list, item)
low = 0
high = list.length - 1
while low <= high
    mid1 = low + (high - low) / 3
    mid2 = high - (high - low) / 3
    if list[mid1] == item
        return mid1
    else if list[mid2] == item
        return mid2
    else if list[mid1] > item
        high = mid1 - 1
    else if list[mid2] < item
        low = mid2 + 1
    else
        low = mid1 + 1
        high = mid2 - 1
return -1

Ternary Search algorithms implementation:

int TernarySearch(int[] list, int item) {
int low = 0;
int high = list.Length - 1;
while (low <= high) {
    int mid1 = low + (high - low) / 3;
    int mid2 = high - (high - low) / 3;
    if (list[mid1] == item) {
        return mid1;
    }
    else if (list[mid2] == item) {
        return mid2;
    }
    else if (list[mid1] > item) {
        high = mid1 - 1;
    }
    else if (list[mid2] < item) {
        low = mid2 + 1;
    }
    else {
        low = mid1 + 1;
        high = mid2 - 1;
    }
}
return -1;
}

These are just a few of the many searching algorithms available. Each algorithm has its own strengths and weaknesses and the best algorithm to use depends on the specific problem you are trying to solve and the characteristics of the data you are working with. It is important to understand the underlying principles and time complexity of each algorithm so that you can make an informed decision about which one to use in a given situation.

Conclusion

Searching algorithms may seem daunting at first, but with a bit of understanding and practice, they can be a powerful tool in your arsenal. Whether you’re using a simple linear search or a more advanced algorithm like jump search, being able to quickly and efficiently find what you’re looking for can make a big difference in your program’s performance. So next time you’re faced with a search problem, don’t be afraid to give one of these algorithms a try!