#704 - Binary Search - LeetCode
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.
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 an ascending order.
This is quite straight forward. The problem states that we need to find the
target from a
O(log n) time. Whenever you see that the array is sorted and that the expected time complexity is
O(log n), the first thing that has to come to your mind is Binary Search.
Most importantly, this problem's title says binary search 😂😂. So, just perform binary search on the array and return the index.
For those of you who don't know what binary search is, don't worry. At the end of this article I've linked an article from GeeksforGeeks, which should help you understand this algorithm.
class Solution: def search(self, nums: List[int], target: int) -> int: low, high = 0, len(nums) - 1 while(low <= high): mid = (low + high) // 2 if nums[mid] == target: return mid elif nums[mid] < target: low = mid + 1 else: high = mid - 1 return -1
In Python, we can use
mid = (low + high) // 2 without any consequences, but in other programming languages like Java and C++, it is recommended that we use
mid = (low + (high - low)) // 2 so as to avoid the plausible overflow error on doing
low + high.
This approach has a time complexity of
O(log n) and has a space complexity of
- LeetCode Problem Link - Binary Search - LeetCode
- GeeksforGeeks article on Binary Search - Binary Search - GeeksforGeeks