Binary Search Algorithm Flashcards
What is Binary Search?
An algorithm.
Why is it called Binary Search?
Binary meaning two, at each step of the search process, the algorithm splits the search space into two halves, discarding one half based on a comaprison, and continues to search in the other half.
How does Binary Search work?
The process works by repeatedly dividing a sorted array in half, comparing the middle element with the target element, search continues on the left half if it is less than the target value and on the right if it is greater than the target value. This continues until the target value is found or the subarray reduces to zero.
What is the time complexity?
O(log n), where n is the number of element in the array. The logarithmic complexity comes from halving the search space after each comparison.
What is the space complexity?
O(1) for iterative approach because no additional space is required.
O(log n) for a recursive approach due to the stack used during recursion.
Can binary search be used on unsorted arrays?
No, binary search can only be applied to sorted arrays. This is because the assumption is that the elements on one side are greater or lesser than the middle element which is compared with the target value.
What is the difference between iterative and recursive binary search?
Iterative uses a loop to continously divide the array in half while recursive calls itself until it finds the target
What does it mean by search space becomes empty?
The algorithm has reduced the number of elements to search through to zero, indicating that the target value is not present in the array.
