Home » Binary Search in C++

Binary Search in C++

by Online Tutorials Library

Binary Search in C++

We will discuss the binary search in the C++ programming language. Binary search is a mechanism used to find the given elements from the sorted array by continuously halving the array and then searching specified elements from a half array. And the process goes on till the match is found. It works only the sorted data structures. The time complexity of the binary search algorithm is O (log n).

Binary Search in C++

Note: To perform a binary search technique in C++, a programmer or user should ensure the given array must be sorted either be in ascending or descending order.

Algorithm of the binary search in C++

Following is the algorithm to perform the binary search in C++

Steps to perform the binary search in C++

Step 1: Declare the variables and input all elements of an array in sorted order (ascending or descending).

Step 2: Divide the lists of array elements into halves.

Step 3: Now compare the target elements with the middle element of the array. And if the value of the target element is matched with the middle element, return the middle element’s position and end the search process.

Step 4: If the target element is less than the middle element, we search the elements into the lower half of an array.

Step 5: If the target element is larger than the middle element, we need to search the element into the greater half of the array.

Step 6: We will continuously repeat steps 4, 5, and 6 till the specified element is not found in the sorted array.

Example 1: Program to find the specified number from the sorted array using the binary search

Let’s write a program to find the specified number from a sorted array using the binary search in the C++ programming language.

Output

Define the size of the array:   10  Enter the values in sorted array either ascending or descending order:  Arr [0]  = 12  Arr [1]  = 24  Arr [2]  = 36  Arr [3]  = 48  Arr [4]  = 50  Arr [5]  = 54  Arr [6]  = 58  Arr [7]  = 60  Arr [8]  = 72  Arr [9]  = 84  Define a value to be searched from sorted array:  50  Element is found at index 5     

Example 2: Program to perform the binary search using the user-defined function

Output

Element is found at position 5      

In the above program, we declared an array arr[] = {5, 10, 15, 20, 25, 30, 35, 40); and then we specified number ’25’ to which search from the sorted array using the binary search method. Therefore, we create a user-defined function bin_search() that searches the given number and returns the statement “Element is found at position 5″. If the number is not defined in the array, the bin_search() function shows ” Element is not found in the array.”

Example 3: Program to find the specified element using the recursion function

Let’s create an example to check whether the specified element is found in the sorted array using the binary search inside the recursion function.

Output

Define the size of an array: 10  Arr [0] = 2  Arr [1] = 4  Arr [2] = 5  Arr [3] = 8  Arr [4] = 12  Arr [5] = 13  Arr [6] = 27  Arr [7] = 36  Arr [8] = 49  Arr [9] = 51    Enter an element to be searched in ascending array: 12  12 is available at position 6.     

In the above program, we input all elements of an array in ascending order and then define a number as the target element is ’12’, which is searched from a sorted array using the binary search method. So, we create a user-defined function binary_search() that searches the defined element’s position from an array and returns the particular element available at this position. And if the element is not available in the sorted array, it returns 0.


You may also like