C++

C++ Binary Search

C++ comes up with many search methods to search a particular variable from the array or some other data structure. Among all of them, Binary search is quite well-known for its quick response. An array will be converted in half within the binary search while it is already sorted. The comparison would be made by a mid-point of an array. This midpoint value would tell us to search the required value in the left half of an array or the right half. Half of the time for searching will be saved when working with the Binary search method as compared to other searching methods. Thus, within this easy article, we will discuss some examples to illustrate the working of binary search using iterative and recursive search methods.

After opening the terminal shell quickly, you must need a C++ file to create your binary search code in it. Therefore, a simple one-word keyword command, i.e., “touch,” will be utilized for this reason. So, we have been using it to create a C++ file named “binary.cc” and opening it via the built-in GNU Nano editor that comes up with the configuration of the Ubuntu 20.04 system. Both the commands have already been demonstrated with the help of the image below.

Example 01: Iterative Method

The very first method we have been utilizing here is the iterative method of binary search. It would be quite simple to do. After the file has been opened in the nano editor, we have added the header files needed for the code to run. The namespace that must be standard is necessary for C++ code here. A user-defined function named “search” has been created to perform a binary search. This user-defined function takes 4 arguments in its parameters, i.e., “A[]” for array, left for arrays left most value, right for arrays right most value, and v for value to be searched in the array “A”.

Within the start of this function, we have used a simple “while” loop to check whether the leftmost or first value of the array is less than or equal to the right-most value (entered at last) of the array or not. If the value is less than or equal to the right-most value, it will create a new point in the array, i.e., mid. This midpoint has been calculated by using both left and right. After the midpoint has been found, we are using the “if” statement to check if the value at the mid-index of an array “A” is the same as the value requested to be checked, i.e., “v”. If the condition got efficacious and the value “v” matched with the mid-index value, it will return the mid-index of an array. At the start, our array has two halves, left and right. The left one contains smaller values, while the right one contains the bigger values as compared to the mid-index value. When the value at a midpoint is less than the value to be searched, we don’t need to consider the left half of an array because that will contain smaller values.

So, we will be updating our left variable with the index of “mid+1”. On the other hand, if the mid-value is greater than the value requested to be checked, then we need to ignore the right half (bigger values) of an array. So, the right variable will be updated by a new value, i.e., “mid-1”. This process will continue to do until the left of an array is equal to or less than the right point of an array. If non of the conditions are satisfied, we have not found the value in the array and returning -1 as an index to the main method.

Now, came to the main() function implementation. Within this function, we have declared an array named “A” with some integer values in it. The array is already sorted in ascending order. Then a variable “v” has been initialized in which a value entered by a user will be saved. The cout statement tells a user to enter some number while the cin statement is used to collect the user input and save it to the variable “v”.

Another variable, “n” has been defined to get the total size of an array with sizeof() function usage on the array “A”. Another variable, “val” has been used to get the index from the search method as a return value by calling it. The function call passes the array A, left point as 0, right point as integer “n-1”, and the value “v” to be searched. If the search method returns “-1” to variable “val” the first cout statement will be executed; otherwise, the second one will be executed and display the index of a value matched.

Thus the code requires the compilation first. After the first and second execution, the user entered 14 and 19, and it got matched with index 3 and 8, respectively, as displayed. On the third execution, it didn’t work out as shown. So, the g++ compiler is here for your help.

Example 02: Recursive Method

This was all about the iterative method of binary search in C++. Let’s have a second method to do a binary search in C++, a known and recursive method. The recursive method would be the same as the iterative method but recursively call its binary search method. We will be explaining it with the code. So, open the same file and update the search method. We have used the same while loop within the search method with the same conditions in it, i.e., if-else statements, single if statement, and mid-point calculation.

The only change has been performed in the if-else statement of the search function. When the mid-point value is greater than the value to be searched in the search method, and the condition is satisfied, it will call the same search method with little change in its parameters. All the parameters will be the same except the “right” point value, which is now the “mid-1” index. On the other hand, when a mid-point value is less than the value to be searched, i.e., “v” and the condition is not satisfied, it will call the same function with a little change at its parameter argument “left”. The left point will be updated with the index of “mid+1” now.

You can see the main() function is 100% the same as the above iterative example, and it has not a single character change in it.

First, compile this updated recursive code with g++ and then execute it. After the first execution, it returns 3 as a result to value 14, while no index has been found so far for value 24 after the second execution.

Conclusion:

The above whole article is all about binary search in C++. The binary search has been discovered and explained well with two different methods, i.e., iterative and recursive. All the examples implemented and demonstrated are quite simple to do and easy to understand, as every step has been explained quite briefly. Therefore, we are getting high hopes that this article would be equally beneficial for a naïve, new, and expert user.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.