---

📘 Binary Search in an Ordered Array

1️⃣ Introduction

Binary Search is an efficient searching algorithm used to find an element in a sorted (ordered) array.

It works by repeatedly dividing the search space into two halves.

---

2️⃣ Precondition

✔ The array must be sorted (ascending or descending)

---

3️⃣ Working Principle

• Find the middle element
• Compare it with the target (key)
• If equal → element found
• If key < middle → search in left half
• If key > middle → search in right half

Repeat until:

• Element is found OR
• Search space becomes empty

---

4️⃣ Algorithm (Iterative Binary Search)

🔹 Pseudocode

BinarySearch(A, n, key):
   low = 0
   high = n - 1

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

       if A[mid] == key:
           return mid

       else if key < A[mid]:
           high = mid - 1

       else:
           low = mid + 1

   return -1   // element not found

---

5️⃣ Example (Step-by-Step)

🔹 Given Array (Sorted):

A = [2, 5, 8, 12, 16, 23, 38, 56]

🔹 Search Key = 23

---

🔹 Step 1

low = 0, high = 7
mid = 3 → A[3] = 12

23 > 12 → Search right half

---

🔹 Step 2

low = 4, high = 7
mid = 5 → A[5] = 23

✔ Element found at index 5

---

6️⃣ Time Complexity

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

👉 Each step reduces problem size by half.

---

7️⃣ Space Complexity

• Iterative version → O(1)
• Recursive version → O(log n) (stack space)

---

8️⃣ Characteristics of Binary Search

✔ Very efficient for large datasets
✔ Requires sorted data
✔ Reduces search space by half each step

---

9️⃣ Advantages

• Fast searching (logarithmic time)
• Suitable for large data
• Fewer comparisons

---

🔟 Disadvantages

• Works only on sorted arrays
• Not suitable for dynamic data (frequent insert/delete)
• Requires random access (not suitable for linked lists)

---

1️⃣1️⃣ Comparison: Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Requirement	Unsorted OK	Must be sorted
Time Complexity	O(n)	O(log n)
Efficiency	Low	High

---

🔚 Conclusion

Binary Search is one of the most efficient searching algorithms for sorted data.

It works by dividing the search space into halves, leading to logarithmic time complexity.

---

📌 Exam Tip

👉 Always mention:

• Sorted array condition
• Algorithm steps
• Example
• Complexity

---