Explain binary search algorithm
Binary search is an efficient searching algorithm used to find a specific target value within a sorted array or list. It achieves this by repeatedly dividing the search space in half, eliminating half of the remaining elements each time, until the desired value is found or it is determined that the value does not exist in the list.
The algorithm compares the target value with the middle element of the array. If the target value is smaller, it eliminates the right half of the array and continues the search on the left half. If the target value is larger, it eliminates the left half and continues the search on the right half. This process is repeated until the target value is found or the search space is empty.
Binary search has a time complexity of O(log n), which means its runtime grows logarithmically with the size of the input. This makes it significantly faster than linear search for large arrays. However, binary search requires the list to be sorted in ascending or descending order before applying the algorithm.