- C++ Programming Examples
- C++ Programming Examples
- C++: Hello World
- C++: Get Input
- C++: Print Integer
- C++: Add two numbers
- C++: Add, Sub, Multiply, Div
- C++: Add Digits
- C++: Find Average and Percentage
- C++: Find Arithmetic Mean
- C++: Sum of n Natural Numbers
- C++: Sum of n Numbers
- C++: Square's Area and Perimeter
- C++: Rectangle's Area and Perimeter
- C++: Triangle's Area and Perimeter
- C++: Area and Circumference
- C++: Find Simple Interest
- C++: Fahrenheit to Celsius
- C++: Celsius to Fahrenheit
- C++: Print Prime Numbers
- C++: Reverse a Number
- C++: Swap Two Numbers
- C++: Print Multiplication Table
- C++: Find Factorial of a Number
- C++: Find Factors of a Number
- C++: Find HCF and LCM
- C++: Create a Calculator
- C++: Count Digits in a Number
- C++: First and Last Digit Sum
- C++: Product of Number Digits
- C++: Sum of Squares of Digits
- C++: Interchange Digits of Number
- C++ if-else Programs
- C++: Check Even or Odd
- C++: Check Prime or Not
- C++: Check Alphabet or Not
- C++: Check Vowel or Not
- C++: Check Leap Year or Not
- C++: Check Reverse equals Original
- C++: Check Perfect Number
- C++: Check Palindrome or Not
- C++: Check Armstrong or Not
- C++: Divisibility Test
- C++: Find Labor Wage
- C++: Find Discounted Price
- C++: Find Shipping Charge
- C++: Find Telephone Bills
- C++: Calculate Student Grade
- C++: Largest of Two Numbers
- C++: Largest of Three Numbers
- C++ Number Conversion
- C++: Decimal to Binary
- C++: Decimal to Octal
- C++: Decimal to Hexadecimal
- C++: Binary to Decimal
- C++: Binary to Octal
- C++: Binary to Hexadecimal
- C++: Octal to Decimal
- C++: Octal to Binary
- C++: Octal to Hexadecimal
- C++: Hexadecimal to Decimal
- C++: Hexadecimal to Binary
- C++: Hexadecimal to Octal
- C++ Pattern Programs
- C++: Pattern Programs
- C++: Print Diamond Pattern
- C++: Print Floyd's Triangle
- C++: Print Pascal's Triangle
- C++ Array Programs
- C++: 1D Array Program
- C++: Linear Search
- C++: Binary Search
- C++: Largest Element in an Array
- C++: Smallest Element in an Array
- C++: Find Second Largest Element
- C++: Find Second Smallest Element
- C++: Sum of All Elements
- C++: Multiply All Elements
- C++: Element in Even Position
- C++: Element in Odd Position
- C++: Print Even Numbers in Array
- C++: Print Odd Numbers in Array
- C++: Count Even or Odd Numbers
- C++: Sum of Even or Odd Numbers
- C++: Count Positive, Negative, Zero
- C++: Reverse an Array
- C++: Insert an Element
- C++: Delete an Element
- C++: Merge two Arrays
- C++: Bubble Sort
- C++: Selection Sort
- C++: Insertion Sort
- C++: Common Elements
- C++: 2D Array Programs
- C++: Add Two Matrices
- C++: Subtract Two Matrices
- C++: Transpose Matrix
- C++: Multiply Two Matrices
- C++: 3D Array Programs
- C++ String Programs
- C++: Print String
- C++: Find String Length
- C++: Compare Two Strings
- C++: Copy String
- C++: String Concatenation
- C++: Reverse a String
- C++: Delete Vowels from a String
- C++: Delete a Word from a String
- C++: Count Characters in a String
- C++: Count Words in a String
- C++: Frequency of Words
- C++: Remove Spaces from Strings
- C++: Sort a String
- C++: Uppercase to Lowercase
- C++: Lowercase to Uppercase
- C++: Swap Two Strings
- C++: Check the Anagram or Not
- C++: Capitalize All Words in a String
- C++: Get Numbers from a String
- C++ File Programs
- C++: Read a File
- C++: Write Content to a File
- C++: Append Data to a File
- C++: Read and Display File
- C++: Copy a File
- C++: Merge Two Files
- Count Characters in a File
- C++: Capitalize Every Word
- C++: List Files in Directory
- C++: Delete a File
- C++: Encrypt and Decrypt a File
- C++ Misc Programs
- C++: Print ASCII Value
- C++: Add Binary Numbers
- C++: Generate Random Numbers
- C++: Print a Smiling Face
- C++: Days into Years and Months
- C++: Add Two Numbers using Pointer
- C++: Print Fibonacci Series
- C++: Generate Armstrong Numbers
- C++: Find nCr and nPr
- C++: Get IP Address
- C++: Print Date and Time
- C++: Shutdown and Restart Computer
- C++ Programming Tutorial
- C++ Tutorial
C++ Program for Binary Search
In this article, you will learn and get code for searching for an element in an array using the binary search technique in C++ programming. Here are the approaches used:
- Simple binary search program
- Allow the user to define array size and sorts before searching
- binary search in C++, using a user-defined function
- binary search in C++, using recursion
Before going through the above programs, if you're not aware of the binary search technique, you can refer to binary search to understand its logic and algorithm.
Binary Search in C++
To search an element from an array using the binary search technique in C++ programming, you have to ask the user to enter any 10 elements for the array and then enter the element or number to be searched.
After searching the element using the binary search technique, if it is available in the list, display the position of the element. The following C++ program asks the user to enter any 10 array elements and an element to be searched. Here is the simple binary search program:
#include<iostream> using namespace std; int main() { int i, arr[10], num, first, last, middle; cout<<"Enter 10 Elements (in ascending order): "; for(i=0; i<10; i++) cin>>arr[i]; cout<<"\nEnter Element to be Search: "; cin>>num; first = 0; last = 9; middle = (first+last)/2; while(first <= last) { if(arr[middle]<num) first = middle+1; else if(arr[middle]==num) { cout<<"\nThe number, "<<num<<" found at Position "<<middle+1; break; } else last = middle-1; middle = (first+last)/2; } if(first>last) cout<<"\nThe number, "<<num<<" is not found in given Array"; cout<<endl; return 0; }
This program was built and runs under the Code::Blocks IDE. Here is the initial snapshot of the sample run:
Now enter any 10 numbers (in ascending order) as array elements, say 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, and then a number that is going to be searched from the list, say 8. Here is the final snapshot of the sample run:
If the user enters 10 elements as 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and the element to be searched as 8, the above program will run as follows:
- 10 elements get stored in the array arr[] in a way that arr[0] = 1, arr[1] = 2, arr[2] = 3, and so on.
- The number to be searched, say 8, gets initialized to num. Therefore, num=8
- Initially, first = 0 and last = 9.
- (first+last)/2 or 0+9/2 or 4 gets initialized to middle. Therefore middle=4
- Because the value of first (0) is less than the value of last (9), the condition of the while loop evaluates to be true. Therefore, program flow goes inside the loop
- checks whether arr[middle]<num evaluates to be true or not. When the values of variables middle and num are entered, arr[4]<num or 5<8 evaluates to be true. As a result, program flow enters the if block, and middle+1, 4+1, or 5 is set to first.
- Because the condition of the if block evaluates to true, the statement(s) of the else if and else block will not be executed.
- At last, middle = (first+last)/2, or middle = (5+9)/2, or middle=7.
- Program flow goes back to the condition of the while loop. The condition first <= last, or 5<=9 again evaluates to be true; therefore, again, program flow goes inside the loop.
- Checks whether the if block's condition, arr[middle]<num, evaluates to true or false, that is, arr[7]<num or 8<8 evaluates to false. As a result, program flow proceeds to the else if block and checks its condition.
- The condition arr[middle]==num or 8==8 is satisfied. Therefore, program flow goes inside this else if block and executes its statements.
- That is, it prints the position of the number, because the number is found at index number 7. Therefore, I've printed its position as 8, since indexing in arrays starts from 0, not from 1.
- After printing the position of the element, use the break keyword to break out of the while loop.
- After exiting the while loop, check the condition using the if block, that is, whether first's value is greater than the value of last or not.
- If condition is true, print a message indicating that the number was not found in the list.
Allow the user to define the size
This program allows the user to define the size of the array. It also doesn't care about the way the user enters the data, that is, either in ascending or random order. Because, after receiving all the numbers, we've created a block of code that sorts the list in ascending order (before performing the search operation). Then, as shown in the program below, ask for an element to be searched from the sorted list:
#include<iostream> using namespace std; int main() { int len, i, arr[50], num, j, temp, first, last, middle; cout<<"Enter the Size: "; cin>>len; cout<<"Enter "<<len<<" Elements: "; for(i=0; i<len; i++) cin>>arr[i]; // sort the array first for(i=0; i<(len-1); i++) { for(j=0; j<(len-i-1); j++) { if(arr[j]>arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } // print the sorted array cout<<"\nThe New Sorted Array is:\n"; for(i=0; i<len; i++) cout<<arr[i]<<" "; // now back to binary search cout<<"\n\nEnter Element to be Search: "; cin>>num; first = 0; last = (len-1); middle = (first+last)/2; while(first <= last) { if(arr[middle]<num) first = middle+1; else if(arr[middle]==num) { cout<<"\nThe number, "<<num<<" found at Position "<<middle+1; break; } else last = middle-1; middle = (first+last)/2; } if(first>last) cout<<"\nThe number, "<<num<<" is not found in given Array"; cout<<endl; return 0; }
Here is its sample run, supposing that the user enters the array size as 5 and its elements as 5, 1, 4, 2, and 3:
Now enter an element, say 4, to search it from the list, and print its position as shown in the output given below:
To learn more about sorting an array, you can follow and apply any of the below sorting methods in the program:
Binary search in C++, using user-defined functions
This program is created using a user-defined function, binSearRecFun(), that receives three arguments. The first is the array, the second is the number to be searched, and the third is the array's size.This function either returns the position of the element in the list or a value of 0 that indicates the number is not available in the list.
Before the binary search, there is also a function called sortArray() that sorts the given array in ascending order.
#include<iostream> using namespace std; void sortArray(int [], int); int binSearchFun(int [], int, int); int main() { int len, i, arr[50], num, pos; cout<<"Enter the Size (max. 50): "; cin>>len; cout<<"Enter "<<len<<" Elements: "; for(i=0; i<len; i++) cin>>arr[i]; // sort the array first sortArray(arr, len); // print the sorted array cout<<"\nThe New Sorted Array is:\n"; for(i=0; i<len; i++) cout<<arr[i]<<" "; cout<<"\n\nEnter Element to be Search: "; cin>>num; // search element using binary search pos = binSearchFun(arr, num, len); if(pos==0) cout<<endl<<num<<" isn't available in the list"; else cout<<endl<<num<<" is available at Position "<<pos; cout<<endl; return 0; } void sortArray(int arr[], int len) { int i, j, temp; for(i=0; i<(len-1); i++) { for(j=0; j<(len-i-1); j++) { if(arr[j]>arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } int binSearchFun(int arr[], int num, int len) { int first, last, middle; first = 0; last = (len-1); middle = (first+last)/2; while(first <= last) { if(arr[middle]<num) first = middle+1; else if(arr[middle]==num) return (middle+1); else last = middle-1; middle = (first+last)/2; } return 0; }
Here is its sample run, supposing that the user enters the size as 6, its elements as 6, 1, 5, 2, 3, and 4, and the number to be searched as 4:
Binary search in C++ using recursion
This program uses recursion (a function that calls itself) to search an element using the binary search technique.
#include<iostream> using namespace std; int binSearRecFun(int [], int, int, int); int main() { int i, arr[10], num, pos; cout<<"Enter 10 elements (in ascending order): "; for(i=0; i<10; i++) cin>>arr[i]; cout<<"\nEnter element to be search: "; cin>>num; pos = binSearRecFun(arr, 0, 9, num); if(pos==0) cout<<endl<<num<<" is not available in the list"; else cout<<endl<<num<<" is available at Position "<<pos; cout<<endl; return 0; } int binSearRecFun(int arr[], int first, int last, int num) { int middle; if(first>last) return 0; middle = (first+last)/2; if(arr[middle]==num) return (middle+1); else if(arr[middle]>num) binSearRecFun(arr, first, middle-1, num); else if(arr[middle]<num) binSearRecFun(arr, middle+1, last, num); }
Here is its sample run:
The same program in different languages
« Previous Program Next Program »