Binary Search LeetCode

Binary search is an efficient, search algorithm that searches for an element in a sorted array by repeatedly dividing the search interval in half. For an array of size nn, the Linear search algorithm takes a time complexity of O(n)O(n) to search an element in the array. On the other hand, if the array is sorted, binary search reduces the time complexity to just O(log(n))O(log (n)).

Example

We unknowingly use this algorithm throughout our everyday lives without noticing it. Suppose we are using a physical dictionary to find the meaning of the word “Mysterious.” We will start our search by browsing the first letter, “M.” Since the dictionary is sorted lexicographically and “M” is the middle letter of the English alphabet, we similarly open the middle page in the dictionary. Then, if the current page contains words starting with a lower alphabet than “M,” we update our search to browse to the next pages, and we browse in previous pages if the current words start with a higher alphabet than “M.” If the words in the current page start with “M,” we then repeat the same process but this time using the next letter in our word, “Mysterious,” which is “Y” until we have found our word. The following example highlights the above process of finding the word “Mysterious” in a dictionary.

Open the middle page in dictionary
Open the middle page in dictionary
1 of 4

Problem statement

We will now see the working of the binary search algorithm in action. Consider we have a sorted array, and we need to search the array for the target and return its index if it is found. Otherwise, we return -1.

Sample input:

nums = [1,4,5,7,18,30,41,60,85]
target = 60

Sample output:

7

Constraints:

  • 1 <= nums.length <= 104

  • -104 < nums[i], target < 104

  • All the integers in nums are unique.

  • nums is sorted in ascending order.

Algorithm

Here’s how the algorithm works:

  1. Initialize two pointers, left and right to the first and last index of the array, respectively.

  2. Now iterate the array until left pointer becomes equal to right pointer and perform following steps:

    1. Calculate value of mid pointer using the formula, mid=(left+right)/2mid=(left+right)/2.

    2. If value pointed to by mid is equal to the value of target, we return mid.

    3. If the value pointed to by mid is bigger than target, then we shift the right pointer to one index before mid.

    4. If the value pointed to by mid is smaller than target, we shift the left pointer one index after mid.

Find the target in the sorted array.
Find the target in the sorted array.
1 of 8

Knowledge test

Test your understanding of the problem with the quiz below:

Choose the correct answer.

Q

Given the sorted array [-12, 10, 18, 23, 29, 32], and target 12, what is the output of the binary search algorithm?

A)

-1

B)

0

C)

6

D)

12

Code example

Let’s explore iterative and recursive solutions to the binary search algorithm.

Iterative solution

Below is the code implementation of the iterative solution to the binary search algorithm:

def binary_search_iterative(arr,target):
  left=0
  right=len(arr)-1
  while left!=right:
    mid=(right+left)//2
    if arr[mid]==target:
      return mid
    elif target<arr[mid]:
      right=mid-1
    else:
      left=mid+1
  return -1
arr = [1,4,5,7,18,30,41,60,85]
print(binary_search_iterative(arr,60))

Code explanation

Here is the step-by-step breakdown of the solution that we implemented:

  • Lines 2–3: Initially, we set the left and right pointers pointing to the first and last elements of arr, respectively.

  • Line 4: We initialize a while loop that will run until the left and right pointers point to the same element so we can avoid an infinite loop.

  • Line 5: We calculate mid which points to the middle of the sub-array, whose boundaries are specified by the left and right pointers.

  • Lines 6–7: We return mid index if we have found the target.

  • Lines 8–9: Since the array is sorted, if arr[mid] > target, it means that the target element should be toward the left of mid. So we update the right pointer to mid-1.

  • Lines 10–11: If arr[mid] < target, it means that the target element should be toward the right of mid. So we update the left pointer to mid+1.

  • Line 12: Finally, we return -1 if the target is not found in arr.

Time complexity: The time complexity of the iterative solution is O(log(n))O(log(n)), since we divide the search space by half in each iteration, and it takes log(n)log(n) steps to reduce the search space from nn to 11 in the following sequence: n,n2,n4,...,1n,\frac{n}{2},\frac{n}{4},...,1.

Space complexity: The space complexity of the iterative solution is O(1)O(1), since no extra space is used.

Recursive solution

Below is the code implementation of the recursive solution to the binary search algorithm:

def binary_search_recursive(arr,target,left,right):
  if left<right:
  
    mid=(right+left)//2
    if arr[mid]==target:
      return mid
    elif target<arr[mid]:
      return binary_search_recursive(arr,60,left,mid-1)
    elif target>arr[mid]:
      return binary_search_recursive(arr,60,mid+1,right)
  else:
      return -1
arr=[1,4,5,7,18,30,41,60,85]
print(binary_search_recursive(arr,60,0,len(arr)-1))

Code explanation

Here is the step-by-step breakdown of the solution that we implemented:

  • Line 1: For the recursive solution, we also pass left and right , which are indexes for the first and last elements of arr respectively.

  • Line 3: We create a condition to continue the recursion until the left pointer becomes equal to the right pointer.

  • Line 5: We calculate mid which points to the middle of the sub-array, whose boundaries are specified by the left and right pointers.

  • Lines 6–7: We return mid index if we have found the target.

  • Lines 8–9: Since the array is sorted, if arr[mid] > target, it means that the target element should be toward the left of mid. So we update the right pointer to mid-1 and call the function recursively with the updated parameters.

  • Lines 10–11: If arr[mid] < target, it means that the target element should be toward the right of mid. So we update the left pointer to mid+1 and call the function recursively with the updated parameters.

  • Line 12: Finally, we return -1 when left==right.

Time complexity: The time complexity of the recursive solution is O(log(n))O(log(n)), since we divide the search space by half in each iteration until the search space is just one element. So, the depth of the recursion tree becomes log(n)log(n) in the worst case.

Space complexity: The time complexity of the recursive solution O(1)O(1), since no extra space is used.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved