Binary Search

Time complexity: O(log n)

Space complexity: O(1)

Data type: Arrays

Visualization

Comparisons: 0

Delay: 250ms

Items: 50

Definition

Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

Constraints

  • Data in an array must be sorted

Step-by-step explanation

Arguments:

  • target value - key
  • Sorted array - array

Explanation:

  • Divide search space into two halves, by selecting middle index as mid
  • Compare array[mid] with key
  • If array[mid] is equal to key return it's index
  • If array[mid] isn't equal to key, choose next half to be searched
    • If array[mid] is bigger than key, left side of an array should be searched
    • If array[mid] is smaller than key, right side of an array should be searched
  • Repeat until index of key is found or search space is empty

Returns:

Index of key or -1 if not found

Example

1
int binarySearchIterative(const std::vector<int>& arr, int target) {
2
    int left = 0;
3
    int right = arr.size() - 1;
4
    while (left <= right) {
5
        int mid = left + (right - left) / 2;
6
        if (arr[mid] == target)
7
            return mid;
8
        else if (arr[mid] < target)
9
            left = mid + 1;
10
        else
11
            right = mid - 1;
12
    }
13
    return -1;
14
}