Binary Search in Data Structures

In this GoNimbus DSA tutorial, we’ll explore one of the most efficient and widely used searching algorithms — Binary Search.

Binary Search is a powerful method to quickly find a target value within a sorted array by repeatedly dividing the search range in half. Compared to Linear Search, it’s significantly faster, especially for large datasets.

If you already understood Linear Search from our previous tutorial, Binary Search will show you how sorting can drastically improve searching performance.

---

🧩 What is Binary Search?

Binary Search is a divide-and-conquer algorithm used to find a target element in a sorted array.

Instead of checking each element one by one, Binary Search continuously halves the search space:

1. It compares the target value to the middle element.
2. If the target matches the middle element, the search ends.
3. If the target is smaller, the search continues in the left half.
4. If the target is larger, the search continues in the right half.
5. This process repeats until the value is found or the range becomes empty.

---

⚙️ How Binary Search Works

Let’s go through the steps to understand it clearly:

1. Start with two pointers — low at index 0 and high at the last index.
2. Find the midpoint:
   [
   mid = (low + high) // 2
   ]
3. Compare the middle element with the target:
   • If equal → target found.
   • If target < middle element → search in the left subarray.
   • If target > middle element → search in the right subarray.
4. Repeat until the element is found or low exceeds high.

---

🧠 Example: Manual Step-by-Step Search

Let’s manually apply Binary Search to a sorted array.

Array: [2, 4, 6, 8, 10, 12, 14, 16]
Target: 10

Step 1:
Low = 0, High = 7
Mid = (0 + 7) // 2 = 3
Element at mid = 8
Since 10 > 8 → search in the right half.

Step 2:
Low = 4, High = 7
Mid = (4 + 7) // 2 = 5
Element at mid = 12
Since 10 < 12 → search in the left half.

Step 3:
Low = 4, High = 4
Mid = (4 + 4) // 2 = 4
Element at mid = 10
✅ Found target 10 at index 4.

Binary Search efficiently located the target in just 3 comparisons — compared to up to 8 comparisons with Linear Search!

---

💻 Implementation in Python

Here’s how to implement Binary Search in Python (Iterative version):

def binarySearch(arr, targetVal):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == targetVal:
            return mid  # Target found
        elif arr[mid] < targetVal:
            low = mid + 1  # Search in right half
        else:
            high = mid - 1  # Search in left half

    return -1  # Target not found


# Example usage
arr = [2, 4, 6, 8, 10, 12, 14, 16]
targetVal = 10

result = binarySearch(arr, targetVal)
if result != -1:
    print(f"Value {targetVal} found at index {result}")
else:
    print(f"Value {targetVal} not found in the array")

Output:
Value 10 found at index 4

---

🧮 Recursive Implementation

You can also implement Binary Search recursively:

def binarySearchRecursive(arr, low, high, targetVal):
    if low <= high:
        mid = (low + high) // 2
        if arr[mid] == targetVal:
            return mid
        elif arr[mid] < targetVal:
            return binarySearchRecursive(arr, mid + 1, high, targetVal)
        else:
            return binarySearchRecursive(arr, low, mid - 1, targetVal)
    return -1

---

⏱️ Time Complexity Analysis

Case	Description	Time Complexity
Best Case	Target found at the first mid	O(1)
Average Case	Target found after few divisions	O(log n)
Worst Case	Target not found after full division	O(log n)

That’s why Binary Search is much faster than Linear Search for larger datasets.

---

💾 Space Complexity

• Iterative Version: O(1)
• Recursive Version: O(log n) (due to recursive call stack)

---

⚡ When to Use Binary Search

Binary Search is perfect when:

• The data is sorted (ascending or descending).
• You need fast searching performance.
• Working with large datasets where Linear Search becomes inefficient.

If your array isn’t sorted, you must sort it first before applying Binary Search.

---

🧭 Key Takeaways

• Binary Search divides the array into halves each time.
• Works only on sorted arrays.
• Time Complexity: O(log n)
• Space Complexity: O(1) or O(log n) depending on implementation.
• Much faster than Linear Search for large data.

---

🚀 Conclusion

In this GoNimbus DSA tutorial, you learned how Binary Search works, its logic, step-by-step example, and Python implementation.

It’s one of the most efficient searching techniques and forms the foundation for many advanced algorithms such as Search Trees, Interpolation Search, and Exponential Search.

Continue exploring the GoNimbus DSA Learning Series to master core algorithms that build your problem-solving confidence — one concept at a time!

---