What Is Binary Search in Data Structure With Example?

//

Larry Thompson

Binary search is a fundamental algorithm used in computer science and data structures. It is widely used to search for a specific element in a sorted array or list efficiently. In this article, we will dive deep into understanding what binary search is and how it works, along with an example to illustrate its usage.

Understanding Binary Search

Binary search follows a divide-and-conquer approach to find the desired element. It repeatedly divides the search space in half until the Target element is found or determined to be absent. To perform a binary search, the elements must be sorted in ascending order.

The algorithm’s key steps are as follows:

  1. Set the left and right pointers to the first and last elements of the array, respectively.
  2. While the left pointer is less than or equal to the right pointer, do:
    • Calculate the middle index as (left + right) / 2.
    • If the middle element equals the Target, return its index.
    • If the middle element is greater than the Target, set the right pointer to middle – 1.
    • If the middle element is less than the Target, set the left pointer to middle + 1.
  3. If no match is found after exhausting all possibilities, return -1 to indicate that the Target element does not exist in the array.

An Example of Binary Search

To better understand binary search, let’s consider an example. We have a sorted array [2, 4, 6, 8, 10] and want to find if it contains the number 6. Let’s walk through each step of binary search:

Step 1: Set the left pointer to the first element, which is 2, and the right pointer to the last element, which is 10.

Step 2: Calculate the middle index as (0 + 4) / 2 = 2. The middle element is 6.

Step 3: Since the middle element is equal to our Target, we have found it! The index of 6 in the array is 2.

As we can see from this example, binary search successfully located the Target element in just a few steps. This algorithm’s time complexity is O(log n), making it highly efficient for large datasets compared to linear search algorithms with a time complexity of O(n).

Conclusion

In summary, binary search is a powerful algorithm used to efficiently search for an element in a sorted array or list. By repeatedly dividing the search space in half, it quickly narrows down the possibilities until either finding the Target or determining its absence. Remember that binary search requires a sorted dataset to work correctly.

We hope this article has provided you with a comprehensive understanding of binary search and its usage. Now you can apply this knowledge in your programming endeavors to optimize searching operations!

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy