DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Binary Search - Solution
Solutions and explanations
Link to Problem StatementView on GitHubWatch Video

Video Explanation

Binary Search is an efficient algorithm used to find an element in a sorted array.
Instead of scanning each element sequentially, it repeatedly divides the search range in half until the target is found or the range becomes empty.

Fun fact:
Even if you have a sorted list with 1 billion elements, Binary Search can still find the target in just 30 steps or less. This is because the algorithm cuts the search space in half at every step — classic log₂(n) behavior.

Here’s how quickly it narrows down:

  • 1,000 items → ~10 steps

  • 1,000,000 items → ~20 steps

  • 1,000,000,000 items → ~30 steps

It’s simple, powerful, and surprisingly easy to get wrong if you're not careful.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        def binary_search(left, right):
            if left > right:
                return -1

            # Calculate the middle index in an overflow-safe way
            mid = left + (right - left) // 2

            if nums[mid] < target:
                return binary_search(mid + 1, right)
            elif nums[mid] > target:
                return binary_search(left, mid - 1)
            return mid
        
        return binary_search(0, len(nums) - 1)

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(log n) — binary search halves the search space at each recursive call.
  • Space Complexity: O(log n) — due to recursion stack.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left , right = 0, len(nums) - 1

        while left <= right:
            # Use left + (right - left) // 2 instead of (left + right) // 2 
            # to avoid overflow in languages with fixed-size integers like C++, Java, etc.
            mid = left + (right - left) // 2
            
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(log n) — binary search halves the search space at each step.
  • Space Complexity: O(1)

import bisect

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)  # Leftmost position to insert target while maintaining order
        if index < len(nums) and nums[index] == target:  # Confirm that the target exists at this index
            return index
        return -1

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(log n)
  • Space Complexity: O(1)