Sorted Array: Binary Search

Binary Search:

Binary search is useful when the input array elements are sorted.

The algorithm divides the search space into half each time the element to be searched (x) is not found. It uses 3 conditions:

1. If the current element of the array is equal to x, then return the index.

2. Else if the current element of the array is less than x, then x will be present towards the right of the current element (because the array is sorted).

3. Else if the current element of the array is greater than x, then x will be present towards the left of the current element.

GeeksForGeeks: Binary Search Example

Code in Python 3:

# Function for binary search
# inputs: sorted array 'arr', key to be searched 'x'
# returns: index of the occurrence of x found in arr 

def binary_search(arr, x):
  l = 0
  r = len(arr)
  
  # while the left index marker < right index marker
  while l < r:
    # find the index of the middle element
    mid = int(l + ((r - l) / 2))

    # if middle element is x, return mid
    if arr[mid] == x:
      return mid
    
    # if middle element is < x, update l to search to the right of mid
    elif arr[mid] < x:
      l = mid + 1
      
    # if middle element is > x, update r to search to the left of mid
    else:
      r = mid -1
    
  return -1

Example:

Let the input array be: [1, 2, 6, 10, 13, 20, 25, 26, 27, 30] 
and x = 20

initially: l = 0, r = 9, mid = 0 + (9 - 0) / 2 = 4
1. l = 0, r = 9, mid = 4
    l < r: 
    arr[mid] = 13
    arr[mid] < x -> l = mid + 1
                             l = 4 + 1 = 5
   mid = 5 + (9 - 5) / 2
   mid = 5 + 2 = 7

2. l = 5, r = 9, mid = 7
    l < r: 
    arr[mid] = 26
    arr[mid] > x -> r = mid - 1
                             r = 7 - 1 = 6
   mid = 5 + (6 - 5) / 2
   mid = 5 + 0 = 5

3. l = 5, r = 6, mid = 5
    l < r: 
    arr[mid] = 20
    arr[mid] = x -> element found -> return mid

Time Complexity:

As we can see, the search space gets reduced by half after each iteration if the element is not found, hence binary search has a time complexity better than the linear array search.

if there are 16 elements in array:
after 1st iteration if 'x' not found then elements = 8
after 2nd iteration if 'x' not found then elements = 4
after 3rd iteration if 'x' not found then elements = 2
after 4th iteration if 'x' not found then elements = 1
The search space is decreasing logarithmically. Log(16) = 4

Hence, Binary Search time complexity is O(log n) where n is the number of elements in the sorted array.

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal