Binary Search is a Divide and Conquer search algorithm. It uses O(log n) time to find the location of an item in a search space where n is the size of the search space. In this article, I will introduce you to the binary search algorithm using C++.
Introduction to Binary Search
Binary search works by halving the search space on each iteration after comparing the target value to the median value of the search space. Before learning its implementation using C++, I suggest you to first learn the implementation of Linear search from here.
To use a binary search, the search space must be ordered (sorted) in some way. Duplicate entries (those that compare as equal according to the compare function) cannot be distinguished, although they do not violate the binary search property.
By convention, we use less than operator as a comparison function. If a < b, it will return true. If a is not less than b and b is not less than a, a and b are equal.
Let’s take a look at the example below to see how binary search works:
- It launches the search in an array sorted in descending order.
- At each step, it selects the middle element of the array and compares it to the search element. If the element values ​​are equal, return the index of the element. If it finds that the element is greater than the desired element, it searches for it in the left subarray. If the item is greater than the desired value, search the right sub-array.
- It continues to repeat the steps on the new sub-array until it finds the desired value.
Implementation of Binary Search Using C++
Now let’s see how to implement the binary search algorithm using the C++ programming language. I will use the steps mentioned above to implement binary search in C++:
This is how we can implement a binary search in the C++ programming language. If you want to learn its implementation using Python, you can check out this article here.
Hope you liked this article on the implementation of binary search in the C++ programming language. Please feel free to ask your valuable questions in the comments section below.
