Binary Search vs Linear Search in Python

Binary Search is an half-interval search algorithm that is used to find the index for a target value in a sorted array. Binary Search is faster than Linear Search (Sequential Search) if the array not is to small. Binary Search requires that an array is sorted. Linear Search works with an unsorted array.

Linear Search runs in linear time O(n), it must iterate over all the elements in the array in the worst case. Binary Search runs in logarithmic time O(log n), in the example below it only needs 5 steps in the worst case (size of the array is 19 elements). Linear Search means that we iterate the search space sequentially until we find the target value. Binary Search means that we always search in the middle of the search space and are able to ignore parts of the search space.

Example

We start with an unsorted list of randomly generated integers and want to find a target value of 12 in the array. You can set the target value to a number that does not exist in the array to find out the worst case performance.

# Random integers in unsorted list
numbers = [1, 42, 7, 62, 59, 43, 10, 81, 62, 68, 58, 53, 46, 74, 12, 96, 66, 19, 31]

# Set the number to be found
target = 12

# Linear search
steps = 0
for i in range(len(numbers)):
    steps += 1
    if(numbers[i] == target):
        print('Linear search found target at index {0} in {1} step(s)'.format(i, steps))
        break

# Binary search (numbers must be sorted)
numbers.sort()
print('Sorted numbers: {0}'.format(numbers))
steps = 0
start = 0
end = len(numbers) - 1
while (start <= end):
    
    # Increase steps
    steps += 1

    # Calculate mid index
    mid = int((start + end) / 2)
          
    # Check if target is in middle
    if (numbers[mid] == target): 
        print('Binary search found target at index {0} in {1} step(s)'.format(mid, steps))
        break
    elif (numbers[mid] < target): 
        start = mid + 1 # Restrict search space to right half
    elif (numbers[mid] > target):
        end = mid - 1 # Restrict search space to left half

Output

Linear search found target at index 14 in 15 step(s)
Sorted numbers: [1, 7, 10, 12, 19, 31, 42, 43, 46, 53, 58, 59, 62, 62, 66, 68, 74, 81, 96]
Binary search found target at index 3 in 5 step(s)