Explanation
- Binary Search is an efficient algorithm used to find an element in a sorted list or array. It works by dividing the list into two halves and repeatedly narrowing down the search space until the target element is found.
-
-
Steps:
- The list must be sorted first.
- Start with the low pointer at index 0 and the high pointer at the last index of the list.
- Find the middle element:
mid = (low + high) // 2. - Compare the middle element with the target:
- If the middle element is equal to the target, return the index.
- If the middle element is greater than the target, the target must be in the left half, so set
high = mid - 1. - If the middle element is smaller than the target, the target must be in the right half, so set
low = mid + 1.
- This process repeats until the target element is found or the search space is exhausted.
-
Time Complexity:
- The time complexity of Binary Search is O(log n), where n is the number of elements in the list or array.