Solution: Binary Search

Statement

We are given an array of integers, nums, sorted in ascending order, and an integer value, target. If the target exists in the array, return its index. If the target does not exist, return -1.

Constraints:

• $1$$\leq$ nums.length $\leq$ $10^3$

• $-10^4$$\leq$ nums[i] , target $\leq$ $10^4$

• All integers in nums are unique.

• nums is sorted in ascending order.

Solution

Binary search locates a target value in a sorted array by repeatedly dividing the search space in half. We compare the target with the middle element, starting with the entire array. If they match, we return the index. If the target is smaller, we narrow the search to the left half; if larger, we search the right half. This process continues until the target is found or the search space is exhausted.

We can solve the above problem using the iterative approach by following the steps below:

1. Initialize low to 0 and high to nums.length - 1.

2. While low is less than or equal to high:

   1. Compute mid using the formula $mid = low + ((high - low) / 2)$

      1. ​If nums[mid] is equal to the target, return mid.

      2. If nums[mid] is greater than the target, update high = mid - 1 to search in the left half.

      3. If nums[mid] is less than the target, update low = mid + 1 to search in the right half.

   2. Repeat the process by recalculating mid in each iteration.

3. If low becomes greater than high, return -1, indicating that the target is not in the array because the algorithm has checked all the positions where the target could be.

Let’s look at the following illustration to get a better understanding of the algorithm: