Insertion Sort and Binary Search


Insertion Sort Code:

import time
def insertionSort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key
# Driver code to test above
a = int(input("Enter a number:"))
b = int(input("Enter a number:"))
c = int(input("Enter a number:"))
d = int(input("Enter a number:"))
e = int(input("Enter a number:"))

arr = [a, b, c, d, e]
print ("Sorted array is:")

Binary search code:
def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            print("Your number was found")
        elif target > val:
            if lower == x:   # this two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x
a = int(input("Please enter a number between 1 and 10:"))
binary_search([1,5,8,10], a)

In insertion sort, the code looks through the numbers and recognises whether a number is larger or smaller than previously checked numbers. This sorting method actually looks at all previously checked numbers instead of just the previous one. Insertion sort inserts a number where it fits. 

Binary search is an effective search method which uses a middle number to search for another number. In binary search, the middle element in the array is compared to the number that needs to be found. If the number is bigger, then the middle number and everything smaller is removed, but if it is smaller, the middle number and everything bigger is removed. This process is continued until the number is found.


Binary Search Code:

Insertion Sort Code:

How does insertion sort work:

How does Binary Search work:

Leave a Reply

Your email address will not be published. Required fields are marked *