binary search

Binary search is a searching technique that finds the position of a target value within a sorted list. In this searching technique target element match the middle value of the list if not found then it moves to the half of the list and the half list is eliminated on which cannot lie. Again search the element in the remaining half list and this process continues to repeat till the target value is found or declare an element do not exist.

#include <bits/stdc++.h> using namespace std; int binarySearch(int arr[], int left, int right, int key) { if (right >= left) { int mid = left + (right - left) / 2; // If the element is present at the middle itself. if ( arr[mid] == key ) { return mid; } // If element is smaller than find in left side. if ( arr[mid] > key ){ return binarySearch(arr, left, mid - 1, key); } // else element in right side. return binarySearch(arr, mid + 1, right, key); } //If key is not exist in array. return -1; } int main() { // Array of elements. int arr[] = {1,4,7,11,16,19,23,28,30,31,40,78,105,201}; // Length of array int arrayLength = sizeof( arr ) / sizeof( arr[0] ); // Key that need to find in array. int key = 201; int index = binarySearch( arr, 0, arrayLength - 1, key ); if ( index != -1 ) { cout<<"Found element at position : "<<index<<endl; } else { cout<<"Given element is not exist in array"<<endl; } return 0; }

**Key Points:**

- Binary search is also known as a
**half-interval search**,**logarithmic search**or**binary chop**. - This search algorithm works on the principle of divide and conquer.
- Binary search is worked with a sorted list.
- The time complexity of this searching technique is O( log n ).
- Binary search is faster than
**linear**and**jump**search.

LEAVE A COMMENT

## Leave a Reply