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:
nums.length
nums[i]
,target
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:
Let’s initialize the
low
andhigh
variables toand nums.length-1
, respectively.Calculate the
mid
index using the formula. If
nums[mid]
is equal to thetarget
value, we returnmid
.If
nums[mid]
is greater thantarget
, pointhigh
tomid-1
, and the value oflow
remains the same. Now we will search the left part of the array.If
nums[mid]
is less thantarget
, pointlow
tomid + 1
, and the value ofhigh
remains the same. Now we will search the right part of the array.
When the value of
low
is greater than the value ofhigh
, this indicates that thetarget
is not present in the array. This is because we’ve checked all possible positions wheretarget
might exist. So,-1
is returned.
Let’s look at the following illustration to get a better understanding of the algorithm:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.