Skip to main content

Binary Search (Geeks for Geeks)

Binary Search is a highly efficient search algorithm used to find the position of a target element within a sorted list. It works by repeatedly dividing the search interval in half and comparing the target value to the middle element of the interval.

  1. Start with the left pointer at the beginning of the list and the right pointer at the end.
  2. Calculate the middle index of the current search interval.
  3. Compare the target value with the middle element:
    • If the target value equals the middle element, return the middle index.
    • If the target value is less than the middle element, move the right pointer to middle−1middle - 1.
    • If the target value is greater than the middle element, move the left pointer to middle+1middle + 1.
  4. Repeat steps 2-3 until the left pointer exceeds the right pointer.
  5. If the target value is not found, return -1.

How does Binary Search work?​

  • It starts by comparing the target value to the middle element of the list.
  • If the target value matches the middle element, the search is complete.
  • If the target value is less than the middle element, the search continues in the left half of the list.
  • If the target value is greater than the middle element, the search continues in the right half of the list.
  • This process continues until the target value is found or the search interval is empty.

Example for Binary Search(GFG)

Problem Description​

Given a sorted list and a target element, implement the Binary Search algorithm to find the index of the target element in the list. If the element is not present, return -1.

Examples​

Example 1:

Input:
list = [1, 3, 5, 7, 9]
target = 5
Output: 2

Example 2:

Input:
list = [2, 4, 6, 8, 10]
target = 7
Output: -1

Your Task:​

You dont need to read input or print anything. Complete the function binarysearch() which takes arr[], N and K as input parameters and returns the index of K in the array. If K is not present in the array, return -1.

Expected Time Complexity: O(LogN)O(LogN) Expected Auxiliary Space: O(LogN)O(LogN) if solving recursively and O(1) otherwise.

Constraints​

  • 1<=N<=1051 <= N <= 10^5
  • 1<=arr[i]<=1061 <= arr[i] <= 10^6
  • 1<=K<=1061 <= K <= 10^6

Implementation​

Written by @ngmuraqrdd
def binary_search(lst, target):
left, right = 0, len(lst) - 1
while left <= right:
mid = left + (right - left) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

Complexity Analysis​

  • Time Complexity: O(logn)O(log n), where nn is the number of elements in the list. The list is divided in half at each step, leading to logarithmic time complexity.
  • Space Complexity: O(1)O(1), as no extra space is required apart from the input list.

Advantages and Disadvantages​

Advantages:

  • Highly efficient for large sorted lists.
  • Fast search time due to logarithmic time complexity.

Disadvantages:

  • Requires the list to be sorted.
  • Less efficient for small lists compared to linear search.

References​