Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
To achieve a time complexity of O(log n), we can use binary search algorithm.
The idea of binary search is to divide the search space in half at each step. We start by setting two pointers, ‘left‘ and 'right‘, to the beginning and end of the array, respectively. We then calculate the midpoint of the search space as mid = '(left + right) // 2‘.
We compare the value at the midpoint nums'[mid]' with the target value. If they are equal, we have found the target and return its index mid. If ‘nums[mid] < target‘, we know that the target must be in the right half of the search space, so we move the left pointer to ‘mid + 1‘. Otherwise, we move the right pointer to‘mid - 1‘.
We repeat this process until we find the target or the search space is empty, which is when ‘left > right‘. If we don’t find the target by then, we return -1.
The time complexity of this algorithm is O(log n) because we divide the search space in half at each step, which reduces the search space exponentially.
Let’s understand it with an example:
We have a sorted array: [1, 3, 4, 6, 8, 9, 11], and we need to find 4 in it.
We’d initialise the pointers to extreme ends of array, i.e., left pointer to 0 and right pointer to 1.
Then, we’ll find the middle element, the middle element is 6.
mid = (left + right) // 2 = (0 + 6) // 2 = 3
Since the middle element is greater than the target, the target must be in the left half of the search range.
We’ll repeat the process until we find the solution or dataset is empty.
Solution Code:
Solution 1
By using ‘enumerate‘. It is a built-in Python function that returns an iterator of tuples containing indices and values from an iterable.
class Solution:
def search(self, nums: List[int], target: int) -> int:
for indx, num in enumerate(nums):
if num == target:
return indx
return -1
Solution 2
Using binary search, where we divide the sorted array in half repeatedly until the target element is found, or the search space is empty
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (right + left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
