What Is Binary Search in Data Structure and Algorithm?

//

Angela Bailey

Binary search is an efficient algorithm used to search for an element in a sorted list. It follows a divide-and-conquer approach and is widely used in computer science and data structures. In this article, we will explore the concept of binary search and understand how it works.

What is Binary Search?

Binary search is a searching algorithm that operates on sorted data structures, such as arrays or linked lists. It works by repeatedly dividing the search interval in half until the Target element is found or determined to be absent.

The algorithm starts by comparing the Target element with the middle element of the sorted list. If they are equal, the search is successful, and the algorithm returns the index of the middle element.

If the Target element is less than the middle element, the algorithm continues searching in the lower half of the list. Conversely, if the Target element is greater than the middle element, it continues searching in the upper half of the list. This process continues until either the Target element is found or there are no more elements to search.

How Does Binary Search Work?

To better understand how binary search works, let’s consider an example:

• Step 2: Set two pointers: low and high. The low pointer points to the first element of the list, and high points to its last element.
• Step 3: Calculate mid, which represents the index between low and high: `<mid> = (<low> + <high>) / 2`.
• Step 4: Compare the Target element with the element at index mid.
• If they are equal, the search is successful.
• If the Target element is less than the element at index mid, update high to be one less than mid.
• If the Target element is greater than the element at index mid, update low to be one more than mid.
• Step 5: Repeat steps 3-4 until either the Target element is found or there are no more elements to search.

An Example:

To illustrate binary search, let’s search for the number 7 in a sorted list [1, 3, 5, 7, 9, 11]. We start with:

• Low: points to index 0.
• High: points to index 5.

We calculate the middle index as follows:

`<Mid> = (0 + 5) / 2 = 2.5 (rounded down to the nearest integer) = 2.`

The middle element of our list is at index 2 and has a value of ‘5’.

The Target element ‘7’ is greater than ‘5’, so we update our low pointer as follows:

`<Low> = <Mid> + 1 = 2 + 1 = 3.`

The new low pointer points to index 3, which is the next element in our search interval.

We calculate the midpoint again:

`<Mid> = (3 + 5) / 2 = 4.`

The middle element at index 4 has a value of ‘9’.

The Target element ‘7’ is less than ‘9’, so we update our high pointer as follows:

`<High> = <Mid> - 1 = 4 - 1 = 3.`

Our high pointer now points to index 3, which is the previous element in our search interval.

We calculate the midpoint once again:

`<Mid> = (3 + 3) / 2 = 3.`

The middle element at index 3 has a value of ‘7’, which matches our Target element. Therefore, the search is successful, and the algorithm returns the index of the Target element as ‘3’.

Time Complexity and Space Complexity

Binary search has a time complexity of O(log n), where n is the number of elements in the sorted list. This means that binary search can efficiently handle large lists and performs significantly better than linear search algorithms with a time complexity of O(n).

The space complexity of binary search is O(1) since it only requires a constant amount of additional space for storing pointers and variables used during the search process.

Conclusion

Binary search is an efficient searching algorithm used on sorted data structures. It follows a divide-and-conquer approach to quickly locate the Target element.

By repeatedly dividing the search interval in half, binary search reduces the number of elements to search, resulting in a logarithmic time complexity. This makes it a popular choice for searching applications that deal with large datasets.

By understanding how binary search works and its time and space complexity, you can leverage this algorithm to improve the performance of your applications when dealing with sorted data.