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

The array provided is sorted, so whenever target is greater than any number in the array, target must be present in the subarray to the right of the number. Similarly, whenever target is less than any number in the array, target must be present in the subarray to the left of the number. We can solve the above problem using the iterative approach by following the steps below:

1. Let’s initialize the low and high variables to $0$ and nums.length-1, respectively.

2. Calculate the mid index using the formula $mid = low + ((high - low)/2)$.

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

   2. If nums[mid] is greater than target, point high to mid-1, and the value of low remains the same. Now we will search the left part of the array.

   3. If nums[mid] is less than target, point low to mid + 1, and the value of high remains the same. Now we will search the right part of the array.

3. When the value of low is greater than the value of high, this indicates that the target is not present in the array. This is because we’ve checked all possible positions where target might exist. So, -1 is returned.

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