Illustration of Binary Search Algorithm

Consider the sorted array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

To find the target element 11:

Step 1: Initialize pointers

• left = 0 (start of array)
• right = 9 (end of array)

Step 2: Calculate midpoint

• mid = (left + right) / 2 = (0 + 9) / 2 = 4

Step 3: Compare target with midpoint

• target = 11
• array[mid] = 9

Since target is greater than array[mid], search in the right half.

Step 4: Update pointers based on Step 3

• left = mid + 1 = 5

Step 5: Repeat steps 2-4

• mid = (left + right) / 2 = (5 + 9) / 2 = 7
• array[mid] = 15
• array[mid] > target, then search in the left half.
• right = mid – 1 = 6

• mid = (left + right) / 2 = (5 + 6) / 2 = 5
• array[mid] = 11

Step 6: Target found

• array[mid] == target, we have found the target element. Return the index mid.

Conclusion:

Binary search is a powerful algorithm for efficiently searching sorted arrays or lists. By repeatedly dividing the search space in half, it can quickly locate the target element or determine that it is not present.

Binary search is an efficient search algorithm that works on sorted arrays or lists. It repeatedly divides the search space in half until the target element is found or the search space is exhausted.