DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

2 1

Binary Search

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

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

SOLUTION:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        beg = 0
        end = n - 1
        while beg <= end:
            mid = (beg + end) // 2
            if nums[mid] == target:
                return mid
            elif beg == end:
                break
            elif nums[mid] > target:
                end = mid
            else:
                beg = mid + 1
        return -1
Enter fullscreen mode Exit fullscreen mode
πŸ‘‹ While you are here

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Sentry image

See why 4M developers consider Sentry, β€œnot bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❀️