Read the problem description first. To see the problem, click here.
There is nothing to explain. It’s nothing but a binary search implementation. If you know how to implement Binary Search, then you already know the solution. Since you are in Leetcode, I believe you know this searching algorithm.
If you don’t know binary search, don’t be worried. I will write about the Binary Search Algorithm very soon.
So, today I will share with you just the solution. We can implement a Binary Search iteratively or recursively.
Below is the iterative solution to this problem.
class Solution: def search(self, nums: List[int], target: int) -> int: begin = 0 end = len(nums) - 1 index = -1 while begin <= end: mid = (begin + end) // 2 if target == nums[mid]: index = mid break elif target > nums[mid]: begin = mid + 1 elif target < nums[mid]: end = mid - 1 return index
Below is the recursive solution to this problem.
class Solution: def search(self, nums: List[int], target: int) -> int: def binary_search(lst, start, end, target): if start <= end: mid = (start + end) // 2 if target == lst[mid]: return mid elif target > lst[mid]: return binary_search(lst, mid + 1, end, target) else: return binary_search(lst, start, mid - 1, target) else: return -1 return binary_search(nums, 0, len(nums)-1, target)
It’s an easy problem. If you submit one of the solutions from above in LeetCode, it will be accepted.