How does Binary Search works?
The idea is to compare the middle element with the target value, if the middle element is equal to the target value, the index of the middle element is the position of the target value.
If the target value is smaller than the middle element, the target value is searched in the left half of the current space and If the target value is greater than the middle element, the target value is searched in the right half of the current space. This is done until the target element is found if the element is present in the array.
Examples
Input: arr[] = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}, x = 110
Output: 6
Explanation: Element x is present at index 6.Input: arr[] = {10, 20, 30, 40, 60, 110, 120, 130, 170}, x = 175
Output: -1
Explanation: Element x is not present in arr[].
C++ Program For Binary Search
In this article, we will learn about the Binary Search algorithm and how to implement it in a C++ program.
Binary Search is a search algorithm that is faster than the linear search algorithm. Binary Search is used to search the position of the target element in a sorted array by repeatedly dividing the search space in half. Binary search eliminates half portion of the array with each comparison. It works in a time complexity of O(log n) where n is the number of elements in the array.