BINARY SEARCH ALGORITHM STEP BY STEP

BINARY SEARCH ALGORITHM STEP BY STEP

🎯 What is Binary Search?

Binary Search is a fast searching technique used to find an element in a sorted array by repeatedly dividing the search space into half.

---

📌 Definition

Binary Search is a divide-and-conquer algorithm that finds an element in a sorted list by comparing the target value with the middle element.

---

⚠️ Important Condition

✔ The array must be sorted (ascending or descending)
❌ Binary search does NOT work on unsorted data

---

🧠 How Binary Search Works

Steps:

1. Find middle element
2. Compare middle element with target
3. If match → stop
4. If target is smaller → search left half
5. If target is larger → search right half
6. Repeat until found or range becomes empty

---

📊 Example

Sorted Array:

A = [10, 20, 30, 40, 50, 60, 70]

Target:

Find 50

---

Step-by-step:

Step	Low	High	Mid	Value	Action
1	0	6	3	40	50 > 40 → right half
2	4	6	5	60	50 < 60 → left half
3	4	4	4	50	✅ Found

---

💻 Algorithm (Pseudocode)

BinarySearch(A, key)

1. low = 0
2. high = n - 1

3. while low <= high
4.     mid = (low + high) / 2
5.     if A[mid] == key
6.         return mid
7.     else if key < A[mid]
8.         high = mid - 1
9.     else
10.        low = mid + 1

11. return -1

---

🐍 Python Program for Binary Search

def binary_search(arr, key):
    low = 0
    high = len(arr) - 1

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

        if arr[mid] == key:
            return mid
        elif key < arr[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return -1

# Example
arr = [10, 20, 30, 40, 50, 60, 70]
key = 50

result = binary_search(arr, key)

if result != -1:
    print("Element found at index:", result)
else:
    print("Element not found")

---

Output:

Element found at index: 4

---

⚡ Time Complexity

Case	Complexity
Best Case	O(1)
Worst Case	O(log n)
Average Case	O(log n)

---

📊 Why Binary Search is Fast?

Each step reduces search space by half:

Example:

• 8 elements → 4 → 2 → 1

So it grows very slowly compared to linear search.

---

🆚 Binary Search vs Linear Search

Feature	Linear Search	Binary Search
Data Requirement	Unsorted	Sorted
Speed	Slow (O(n))	Fast (O(log n))
Method	Sequential	Divide & Conquer
Efficiency	Low	High

---

📌 Advantages of Binary Search

• Very fast for large datasets
• Reduces comparisons drastically
• Efficient algorithm

---

❌ Disadvantages

• Requires sorted data
• Not suitable for dynamic/unsorted lists
• More complex than linear search

---

🧠 Real Life Example

• Finding a word in dictionary 📖
• Searching a name in sorted telephone directory 📞

---

📌 Summary

• Binary search works only on sorted data.
• It divides the list into halves repeatedly.
• It is much faster than linear search.
• Time complexity is O(log n).

---

❓ Important Questions

Short Questions

1. What is binary search?
2. What is the condition for binary search?
3. What is time complexity of binary search?
4. What is mid element?
5. Give one real-life example.

---

Long Questions

1. Explain binary search with example.
2. Write algorithm of binary search.
3. Write Python program for binary search.
4. Compare linear and binary search.
5. Explain time complexity of binary search.