这两天阅读了算法图解的第一章和第二章，刚好可以记录一下。

1.二分法

说明：二分法是对已排序的序列进行查找某数的一种算法。要查找一个数在序列的某个位置，也许可以采用从头到尾一个一个地找，如果一共有n个数，那么最坏可能要查找n次。但使用二分法，每次查找就能把范围缩小一半，n可以对半多少次？log2n次！也就是说随着n的增加，二分法的速度要快很多。
二分法：
取序列中间的数与给定的值进行比较，若大于，则取小的那一半序列；反之，取大的那一半序列。再取新序列的中间值与给定数比较，进行同样的判断。直到取到最后一个数。
因为目标值需要对序列中间值进行比较，所以需要取中间位置mid；然后每次比较后都需要更新序列的范围，这个范围可以用high与low进行确定，比较后根据情况把mid值给high或者low，最后返回下标。

def binary_search(array, item):
    """
    二分法：算法复杂度log2n
    input: array一个排序好的序列；item:待查找的值
    return：排序后值所在的下标
    """
    low = 0
    high = len(array) - 1
    #边界条件
    while low <= high:
        mid = (low + high)//2
        if array[mid] == item:
            return mid
        elif array[mid] < item:
            low = mid + 1
        else:
            high = mid - 1
    return None

2.选择排序

说明：每次选择序列中的最小值，将其排到最左边；然后选择剩下位置的最小值，再将其排到剩下位置最左边，直到最后一个位置排好。第一次查询n，第二次查询n-1...第n次1，因此需要查询n(n+1)/2≈n^2
方法1：书中定义了一个查找序列最小值的函数，然后定义了一个空数组来依次接收最小值。

def findSmallest(arr):
    """
    找数组中的最小值的index
    """
    smallest = arr[0]
    smallest_ind = 0
    for i in range(len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_ind = i
    return smallest_ind
#使用额外数组
def selectSort1(arr):
    """
    选择排序：将元素按从小到大排序
    input: 一个数组
    return: 由小到大排序好的数组
    使用额外数组
    """
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest)) #arr要将最小的去掉，而newArr要将最小的加入
    return newArr

根据上面的两段函数，可以把代码进行更改，实现不需要额外的空间。
方法2：每次查找序列的最小值，将最小值与最左边的值进行交换。因为序列每次排序好一个后就需要更新，因此使用两个循环：小循环找到最小值，大循环确定序列的起始值和进行交换的位置。交换两个值，需要一个中间变量用于接收，不然里面的值会被刷新（a<->b: a->c, b->a, c->b）。

def selectSort2(arr):
    """
    选择排序：将元素按从小到大排序
    input: 一个数组
    return: 由小到大排序好的数组
    不使用额外数组
    """
    #设定两个指针，快指针进行遍历-找最小值，慢指针确定起始点
    L = len(arr)
    for i in range(L):
        smallest = arr[i]
        smallest_ind = i
        for j in range(i, L):
            if arr[j] < smallest:
                smallest = arr[j]
                smallest_ind = j
        arr[smallest_ind] = arr[i]
        arr[i] = smallest
    return arr