Solution: Binary Search

Let's solve the Binary Search problem using the Modified Binary Search pattern.

We'll cover the following

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:

  • 11≤\leq nums.length ≤\leq 10310^3

  • −104-10^4≤\leq nums[i] , target ≤\leq 10410^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 00 and nums.length-1, respectively.

  2. Calculate the mid index using the formula mid=low+((high−low)/2)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:

Created with Fabric.js 3.6.6 0 1 2 3 4 5 6 7 8 1 10 20 47 59 63 75 88 99 This is our initial setup. target: 63

1 of 7

Created with Fabric.js 3.6.6 low 0 1 2 3 4 5 6 7 8 1 10 20 47 59 63 75 88 99 mid high target: 63 Let's initialize our low, mid, and high pointers to indexes 0, 4, and 8, respectively.

2 of 7

Created with Fabric.js 3.6.6 low 0 1 2 3 4 5 6 7 8 1 10 20 47 59 63 75 88 99 mid high target: 63 As the value at mid (59) is less than the target value, we will update our low to be mid + 1 (5).

3 of 7

Created with Fabric.js 3.6.6 low 0 1 2 3 4 5 6 7 8 1 10 20 47 59 63 75 88 99 mid high target: 63 We will update the value at mid, which is 75, and discard the left half of the array because our target cannot exist in that range.

4 of 7

Created with Fabric.js 3.6.6 low 0 1 2 3 4 5 6 7 8 1 10 20 47 59 63 75 88 99 mid high target: 63 As the value at mid (75) is greater than the target value, we will update our high to be mid - 1 (5).

5 of 7

Created with Fabric.js 3.6.6 low 0 1 2 3 4 5 6 7 8 1 10 20 47 59 63 75 88 99 mid high target: 63 We will update the value at mid, which is 63, and discard the right half of the array because our target cannot exist in that range.

6 of 7

Created with Fabric.js 3.6.6 low 0 1 2 3 4 5 6 7 8 1 10 20 47 59 63 75 88 99 mid high target: 63 The mid value (63) is equal to the target value. we will return the index (5).

7 of 7

Let’s see how the algorithm above is implemented.

Binary Search

Time complexity#

The time complexity of this solution is logarithmic, O(log⁡ n)O(\log \space n), where nn is the number of elements in the array.

Space complexity#

The space complexity of this solution is constant, O(1)O(1).

Binary Search

First Bad Version