AlgoView

Binary Searching

2
4
7
12
13
17
18
20
23
24
69
90

About algorithm

Explanation

Binary Search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half, significantly reducing the number of comparisons needed.

Steps

  1. Find the middle index of the current search range.
  2. Compare the middle element with the target value.
  3. If they match, the search is complete.
  4. If the target is smaller, search the left half. If larger, search the right half.
  5. Repeat the process until the element is found or the range is empty.

Pseudocode

binarySearch(arr, target):
  low = 0
  high = len(arr) - 1
  while low <= high:
    mid = (low + high) / 2
    if arr[mid] == target:
      return mid
    else if arr[mid] < target:
      low = mid + 1
    else:
      high = mid - 1
      return -1

Complexity

Time: O(log n)

Space: O(1)