704. Binary Search | LeetCode | Python | Solution

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.

Tags: Binary SearchLeetCode