Binary search vs linear search

Source code

Binary search and linear search are two common algorithms used for searching elements in a collection of data. The main difference between them lies in their approach and efficiency.

Linear Search

  1. Linear search checks each element in a list one by one until it finds a match or reaches the end.
  2. If there are n elements in the list, the worst-case scenario is that the element being searched for is at the end of the list or not present at all.
  3. In simple terms, the time taken for linear search increases as the size of the list increases.

Here I make a simple example to illustrate linear search algorithms by looking for the square root of a number. The python codes are as follows:

# calculate square root of a large number using linear search
def square_root_linear_search(n):
    # brute force search from 0 to n
    for i in range(n):
        if i * i == n:
            return i

Binary Search

  1. Binary search is a more efficient algorithm that works only on sorted lists.
  2. It starts by checking the middle element of the list and compares it to the target element being searched for.
  3. If the middle element is the target, the search is successful. Otherwise, binary search determines whether the target is greater or smaller than the middle element and narrows down the search to the left or right half of the list.
  4. By continuously dividing the search space in half, binary search can quickly find the target element or determine that it does not exist in the list.
  5. In simple terms, binary search takes much less time than linear search, especially for large lists, because it can eliminate half of the remaining elements with each comparison.

To compare with linear search algorithms, I make a code to look for the square root of a number using binary search algorithms. The python codes are as follows:

def square_root_binary_search(n):
    start = 0
    end = n
    while start <= end:
        # find the middle number between start and end
        mid = (start + end) // 2
        # compare the middle number with the square root of n
        # if lucky, the square root of n is the middle number
        if mid * mid == n:
            return mid
        # if the square root of n is larger than the middle number, search the upper half
        elif mid * mid < n:
            start = mid + 1
        # if the square root of n is smaller than the middle number, search the lower half
        else:
            end = mid - 1

Now we can compare the two methods to search square root of a large number. The python codes are as follows:


    
# compare two methods to search square root of a number using binary search and linear search
import time

# test the two methods to search square root of a large number
number_input = int(input("input a number to generate a large square number: "))
large_number = number_input ** 2
print("square of an input number {} is {}".format(number_input, large_number))

# test binary search method and time the time used
start = time.time()
sqrt_result_binary_search = square_root_binary_search(large_number)
end = time.time()
print("Time used for binary search:", format(round(end - start, 2), ".2f"), "seconds")
# check the result against the square root of the large number
if sqrt_result_binary_search == number_input:
    print("Result binary search:", sqrt_result_binary_search,
          "is the correct square root of", large_number)
else:
    print("Result binary search:", sqrt_result_binary_search,
          "is not the correct square root of", large_number)

# test linear search method and time the time used
start = time.time()
sqrt_result_linear_search = square_root_linear_search(large_number)
end = time.time()
print("Time used for linear search:", format(round(end - start, 2), ".2f"), "seconds")
# check the result against the square root of the large number
if sqrt_result_linear_search == number_input:
    print("Result linear search:", sqrt_result_linear_search,
          "is the correct square root of", large_number)
else:
    print("Result linear search:", sqrt_result_linear_search,
          "is not the correct square root of", large_number)

The results were:

input a large number: 56789
square of a large number 56789 is 3224990521
Time used for binary search: 0.00 seconds
Result binary search: 56789
Time used for linear search: 0.00 seconds
Result linear search: 56789
input a large number: 5678912
square of a large number 5678912 is 32250041503744
Time used for binary search: 0.00 seconds
Result binary search: 5678912
Time used for linear search: 0.34 seconds
Result linear search: 5678912
input a large number: 56789123
square of a large number 56789123 is 3225004491109129
Time used for binary search: 0.00 seconds
Result binary search: 56789123
Time used for linear search: 3.48 seconds
Result linear search: 56789123

As you can see, binary search takes much less time than linear search, as linear search has to search through alot more than binary search does, however, linear search takes much less time to code. All in all, I think binary search is better for processing large amounts of data while linear search is better for small tasks.