In the previous article, we explored the linear search algorithm, a simple but inefficient searching algorithm in certain situations. The linear search algorithm looks up for the target element in a collection linearly. While this works really well with the smaller datasets, this strategy fails as the dataset grows. So, in this article, we will learn about the binary search algorithm, which is much faster and more powerful compared to linear search. However, this algorithm requires a sorted collection to operate.
Binary Search Algorithm
The Binary Search algorithm works on the divide and conquer principle. It divides a collection into two parts and compares the target to the middle value. If the target matches the middle term, the search is stopped. If the target is smaller than the middle value, the search continues in the left array. If the target is greater than the middle value, the search continues in the right array. This process is repeated unless the target value is not found. If the search reaches the end of the collection and the target is not found, it means that the target does not exist in the collection.
To understand this, consider looking for a contact in the phone book. Instead of directly opening the required contact, you open the phone book randomly and see if the target comes before the opened page or after. If it comes before the opened page, you look in the left pages; if it comes after the opened page, you look in the right pages unless the contact is not found. The binary search works the same.
Demonstration
Let's consider a sorted array [3, 6, 7, 8, 9, 10. 11] to further understand the working of binary search. Suppose we are searching for 6. The Binary search algorithm will operate as follows:
1. Initialize left as 0 (First index_ and right as 4(last index).
2. Find the middle index, i.e. (0+6)/2 = 3. The middle index is 3, and the element is 8. Since 6 < 8, we know the target exists in the left half array.
3. Now, our right becomes the last element (index 2) of the left array, i.e., 7.
4. Again, find the middle, i.e., (0 + 2)/2 = 1. The middle term is 6. We know that 6 = 6. The target is found at index 1.
Implementing Binary Sort Algorithm in C#
Now that you understand how the Binary Search algorithm works, it's time to implement it in C#.
using System;
using System.Collections.Generic;
class Sorting {
static int BinarySearch(int[] numbers, int target)
{
int left = 0; //Assigning the left index
int right = numbers.Length - 1; //Assigning the right index
while (left <= right) //Unless the left becomes larger then the right
{
int middle = (left + right)/2; //Assign the middle index
if(numbers[middle] == target) //If the target exisits at middle
{
return middle; //Return its index
}
else if(numbers[middle] < target) //If the target is bigger than the value in the middle
{
left = middle + 1; //Update left
}
else
{
right = middle - 1; //Update right
}
}
return 0;
}
static void Main() {
int[] nums = {1, 2, 4,5, 6, 7};
int location = BinarySearch(nums, 6); //Calling the Binary search function
if (location != 0) //if location is not 0
{
Console.WriteLine("Item found at " + location); //prints the location of the target
}
else
{
Console.WriteLine("Item not found!");
}
}
}
Time Complexity Analysis
- Best Case: O(1) – The best case is when the target element is present in the middle of the array.
- Average Case: O(log n)- With each iteration, the array is halved. The number of times the n is divided by 2 unless the number of times you can divide 'n' by 2.
- Worst Case: O(log n)- The search space is repeatedly divided unless it becomes empty. The target exists at the end or does not exist at all.
Advantages of Binary Search Algorithm
- The binary search algorithm is highly useful for sorted datasets. Its logarithmic time complexity makes it highly faster than the linear search algorithm.
- It is highly suited for the large and static datasets.
Limitations of Binary Search Algorithm
- The most significant limitation of the binary search algorithm is that it requires the dataset to be sorted before it can perform a search on it. This adds overhead.
- When there are frequent insertions and deletions in the dataset, using binary search can be expensive since maintaining the sorting becomes difficult.
Binary search is a highly efficient and powerful algorithm that works well with sorted large datasets. In this article, we have explored its implementation in C#. Hopefully, you would have understood all the data structures and algorithms we have covered in the tutorial. I recommend you to practice these data structures and algorithms to get a good hands on them. They are really useful in solving numerous programming solutions and come in handy in programming interviews.
