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.

Step-by-Step Guide to Perform Binary Search:

Step 1: Initialize Variables

• low: Set this variable to 0, representing the lower bound of the search space.
• high: Set this variable to the length of the array minus 1, representing the upper bound of the search space.
• target: This is the element you are searching for in the array.

Step 2: Calculate Midpoint

• Find the midpoint of the current search space using the formula: mid = (low + high) / 2.

Step 3: Compare Midpoint to Target

• If array[mid] == target, you have found the target element. Return the index mid.
• If array[mid] < target, the target element must be in the right half of the search space. Set low = mid + 1.
• If array[mid] > target, the target element must be in the left half of the search space. Set high = mid – 1.

Step 4: Repeat Steps 2-3

• Repeat steps 2 and 3 until either the target element is found or low > high.

Step 5: Return Result

• If the target element was found, return the index mid.
• If the target element was not found, return -1 to indicate that the element is not present in the array.

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.