Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the interval is narrowed to the lower half. Otherwise, it is narrowed to the upper half. This process continues until the item is found or the interval is empty.

Common Uses in Competitive Programming:

1. Finding a Target Value: Quickly locating an exact value in a sorted array.
2. Finding Upper/Lower Bounds: Determining the position to insert an element to maintain order.
3. Optimization Problems: Solving problems that can be reduced to a decision problem, often using binary search on the answer.
4. Range Queries: Efficiently handling queries over a range of values.

Binary search is valued for its O(log n) time complexity, making it much faster than linear search for large datasets.

int binary_search(int arr[],int n,int target){
		int low = 0, high = n-1;
		while(low<=high){
				int mid = (low + high)/2;
				if(target==arr[mid]) return mid;
				else if(target>arr[mid]) low = mid+1;
				else high = mid-1;
		}
		return -1;
}

Recursion and Overflow Case

Upper Bound

Lower Bound