Problem statement: You are given a sorted array of integers and a target, your task is to search for the target in the given array. Assume the given array does not contain any duplicate numbers.

1. Iterative Implementation

We will use a couple of pointers i.e. low and high to apply binary search. Initially, the low pointer should point to the first index and the high pointer should point to the last index.

Search space: The entire area between the low and the high pointer(including them) is considered the search space. Here, the search space is sorted.

Algorithm:

Now, we will apply the binary search algorithm in the given array:

• **Divide the search space into 2 halves:**In order to divide the search space, we need to find the middle point of it. So, we will take a ‘mid’ pointer and do the following:mid = (low+high) // 2 ( ‘//’ refers to integer division)
• **Compare the middle element with the target:**In this step, we can observe 3 different cases:
  • If arr[mid] == target: We have found the target. From this step, we can return the index of the target possibly.
  • If target > arr[mid]: This case signifies our target is located on the right half of the array. So, the next search space will be the right half.
  • If target < arr[mid]: This case signifies our target is located on the left half of the array. So, the next search space will be the left half.
• **Trim down the search space:**Based on the probable location of the target we will trim down the search space.
  • If the target occurs on the left, we should set the high pointer to mid-1. Thus the left half will be the next search space.
  • Similarly, if the target occurs on the right, we should set the low pointer to mid+1. Thus the right half will be the next search space.

The above steps will continue until either we found the target or the search space becomes invalid i.e. high < low. By definition of search space, it will lose its existence if the high pointer is appearing before the low pointer.

Dry-run:

Note: If the target is not present in the array, low and high will cross each other.

Note: For a better understanding, please watch the video at the bottom of the page.

Iterative implementation:

• Initially, the pointers low and high will be 0 and n-1(where n = size of the given array) respectively.