This content originally appeared on Level Up Coding - Medium and was authored by Onur Derman
Searching is one of the fundamental tasks in computer science. A search algorithm is a method that is used to find a specific item or record from a collection of items or records. Binary search is one of the most commonly used search algorithms. In this article, we will discuss what binary search is, why it is used, its benefits, and its limitations. We will also provide a C# implementation of binary search with an example list
What is Binary Search?
Binary search is a searching algorithm used to find the position of a target value within a sorted array or list. It works by repeatedly dividing the search interval in half until the target value is found. The algorithm requires the list to be sorted before starting the search. If the list is not sorted, binary search cannot be used.
Why Use Binary Search?
Binary search is a fast and efficient algorithm for searching sorted arrays or lists. It has a time complexity of O(log n), where n is the number of elements in the list. This means that the time taken to find the target value increases logarithmically with the size of the list. For example, if the size of the list is 1 million, binary search will take at most 20 iterations to find the target value. This is much faster than linear search, which has a time complexity of O(n), where n is the number of elements in the list.
Benefits of Binary Search
- Fast and efficient: Binary search is a fast and efficient algorithm for searching sorted arrays or lists.
- Easy to implement: Binary search is easy to implement and requires only a few lines of code.
- Low memory usage: Binary search requires minimal memory usage, making it an ideal algorithm for resource-limited systems.
- Reliable: Binary search is a reliable algorithm that guarantees the target value will be found if it exists in the list.
Limitations of Binary Search
- Sorted list requirement: Binary search requires the list to be sorted before starting the search. If the list is not sorted, binary search cannot be used.
- Static data structure: Binary search is only suitable for static data structures. It cannot be used for dynamic data structures such as linked lists.
C# Implementation of Binary Search
Important Note: You can have the source code from my github repo. The source code is at the end of the article.
The following is an example of binary search implementation in C#:
Let’s try our method with an example. Run the program and see the output.
Output : Element found at index 3
In the above example, BinarySearch method takes an array arr and a target value target as input parameters. It first initializes left and right pointers to the first and last indices of the array respectively. It then enters a while loop and calculates the mid index by taking the average of left and right and rounds it down to the nearest integer.
If the value at the mid index is equal to the target, the method returns mid. Otherwise, it checks whether the value at mid is less than target or greater than target. If it is less than target, it updates left to mid + 1 and repeats the process. If it is greater than target, it updates right to mid + 1 and repeats the process.
Finally, the Main method initializes an array arr and a target value target, and calls the BinarySearch method to find the index of the target value in the array. If the index is found, it prints a message indicating the index. Otherwise, it prints a message indicating that the target value is not found in the array.
Ready for Step-by-Step Demonstration
I want to include a demonstration of every step of the algorithm. The array will be between 0–40 and the target will be 38. Let’s see what the steps of the algorithm will be with the help of the console screen.
Here is the program that I created to demonstrate the steps
This is the output to show what happened inside the algorithm.
In this example, we are searching for the value 38 in an array of integers between 1 and 40. The program outputs the contents of the array, the target value, and then proceeds to perform the binary search algorithm.
As the algorithm progresses, it outputs the current state of the left, right, and mid indices, as well as whether the target value is greater than or less than the middle value. Eventually, the algorithm finds the target value at index 37, and the program outputs a message indicating that the target value was found at that index.
Important Note: In binary search algorithm, the array that we are searching should be a sorted array, otherwise the algorithm will fail to give the correct index of the desired value.
I appreciate your participation and hope that my article has provided you with valuable insights. Thank you for taking the time to read it thus far.
Here is the github link that you can get the source codes:
Medium-Articles/BinarySearch at master · onrdr/Medium-Articles (github.com)
Visualizing Binary Search: Tracing Its Execution Path Step by Step was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Onur Derman
