Given an array of integers
nums which is sorted in ascending order, and an integer
target, write a function to search
target exists, then return its index. Otherwise, return
You must write an algorithm with
O(log n) runtime complexity.
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4
Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1
1 <= nums.length <= 104
-104 < nums[i], target < 104
- All the integers in
numsis sorted in ascending order.
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, ‘
'right‘, to the beginning and end of the array, respectively. We then calculate the midpoint of the search space as
'(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
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.
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
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