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.

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.