Merge sort

Merge sort is a very typical application of divide and conquer. The idea of merging and sorting is to recursively decompose the array, and then merge the array.

After the array is decomposed to the minimum, and then two ordered arrays are merged. The basic idea is to compare the front numbers of the two arrays. Whoever is small will take the first one, and then the corresponding pointer will move back one bit. Then compare again until one array is empty, and finally copy the rest of the other array.

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    # Dichotomous decomposition
    num = len(alist)/2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    # merge
    return merge(left,right)

def merge(left, right):
    '''Merge operation, put two ordered arrays left[]and right[]Merge into a large ordered array'''
    #Subscript pointer of left and right
    l, r = 0, 0
    result = []
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = mergeSort(alist)
print(sorted_alist)

Optimal time complexity: O(nlogn)
Worst time complexity: O(nlogn)
Stability: stable

search

Search is the algorithmic process of finding a specific item in a collection of items. The usual answer to a search is true or false because of whether the item exists. Several common search methods: sequential search, binary search, binary tree search and hash search

binary search

Binary search, also known as half search, has the advantages of less comparison times, fast search speed and good average performance; Its disadvantage is that the table to be checked is required to be an ordered table, and it is difficult to insert and delete. Therefore, the half search method is applicable to the ordered list that does not change frequently but searches frequently. First, assuming that the elements in the table are arranged in ascending order, compare the keywords recorded in the middle of the table with the search keywords. If they are equal, the search is successful; Otherwise, use the intermediate location record to divide the table into the first and second sub tables. If the keyword of the intermediate location record is greater than the search keyword, further search the previous sub table, otherwise further search the next sub table. Repeat the above process until the records that meet the conditions are found and the search is successful, or until the sub table does not exist, the search is not successful at this time.

Binary_search_into_array

Implementation of dichotomy search

(non recursive implementation)

def binary_search(alist, item):
      first = 0
      last = len(alist)-1
      while first<=last:
          midpoint = (first + last)/2
          if alist[midpoint] == item:
              return True
          elif item < alist[midpoint]:
              last = midpoint-1
          else:
              first = midpoint+1
    return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

Recursive implementation

def binary_search(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:
          return True
        else:
          if item<alist[midpoint]:
            return binary_search(alist[:midpoint],item)
          else:
            return binary_search(alist[midpoint+1:],item)

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

Time complexity
Optimal time complexity: O(1)
Worst time complexity: O(logn)