Introduction

The binary search algorithm is a fundamental search technique used in computer science to find the position of a specified value, usually referred to as the "target," within a sorted array or list. The underlying concept of binary search is to divide and conquer by repeatedly eliminating half of the search space until the target is found or the search space is exhausted. Due to its efficiency, binary search is widely used in various applications where data is sorted.

Time Complexity

Binary search offers significant improvements in search efficiency compared to linear search, especially for large datasets. The time complexity of binary search is $O(\log n)$, which is considerably better than the $O(n)$ complexity of linear search. This logarithmic time complexity stems from the way binary search repeatedly divides the search space in half.

How Binary Search Works

Binary search works by following these steps:

1. Initialize: Set two pointers, low and high , which initially point to the beginning and end of the list, respectively.
2. Iterative Process:
   • Calculate the mid index as the average of low and high .
   • Compare the value at mid with the target:
     • If the target matches the value at mid , the search is successful.
     • If the target is less than the value at mid , shift the high pointer to mid - 1 .
     • If the target is greater than the value at mid , move the low pointer to mid + 1 .
3. Repeat: Continue the process until the low pointer exceeds the high pointer, indicating the target is not in the list.

Here is an implementation of binary search in Python:

• First Occurrence: To find the first occurrence of a target with duplicates, extend the binary search by continuing the search towards the beginning even after a match is found.
• Last Occurrence: To find the last occurrence, continue the search towards the end after a match is found.