- Time complexity -
- Space complexity -
Binary search is one of the most commonly used search algorithm on sorted arrays. To search in a sorted array for a specific element, we can repeatedly divide the search range into half.
For example, in the first run, the range is the whole array. If the search key is less than the value at the middle of the array, then the element would be found on the "left" side of the array. Conversely, if the search key is more than the value at the middle of the array, the element would be found on the "right".
"Left" and "right" here refers to the first half and the second half of the array respectively. We repeatedly search in this manner till we find the element or till the interval range is zero.