二分查找(BinarySearch)

二分查找用于在一个有序数组中，查找是否存在目标值，是分治法思维的体现，把大问题对半平分成两个小问题。
下面是尾递归形式的二分查找的伪代码，如果找到，则返回在array中的索引，如果没有找到，就返回-1。

// java
Int BinarySearch(int[] array, int lo, int hi, int key) // 分别是待查找的数组，下限，上限，目标值。
    if (hi<lo) return -1;
    mid = lo + (hi-lo)//2;   # 这里//表示商取整
    if (a[mid] == key):
         return mid;
    if (a[mid] < key):
         return BinarySearch(array, key, mid+1, hi);
    if (a[mid] > key):
         return BinarySearch(array, key, lo, mid-1);

尾递归可以很轻松的写成while循环形式，下面是循环形式的二分查找伪代码。

// java
Int BinarySearch(int[] array, int key)
    lo = 0;
    hi = array.length-1;
    while (hi>=lo) 
        mid = lo + (hi-lo)//2;   # 这里//表示商取整
        if (a[mid] == key):
             return mid;
        if (a[mid] < key):
             lo = mid+1;
        if (a[mid] > key):
             hi = mid-1;
    return -1;

把一个大问题平分成两个小问题，设大问题需要的时间是 $T (n)$ ，则小问题的时间是 $T(\frac{n}{2})$ ，所以递归关系式是 $T(n)=T(\frac{n}{2})+\Theta(1)$ ，解得时间复杂度是 $O (l o g n)$ 。

注意：二分查找随着迭代进行，hi与lo不一定会存在指向同一个位置的情况，很有可能会从[lo,hi]包含两点，直接跳到[lo,hi]是空集的情况。如果忽视这种情况，可能会导致错误。

例如lo=3，hi=4，对应位置的值分别是array[3]=1，array[4]=3，key是0，此时array[mid]=array[3]=1，由于array[mid]>key，则hi=mid-1=2，hi直接就小于lo了。

在java中，对于数组nums可以使用Arrays.binarySearch(nums, lo, hi, target)快捷的进行二分查找，注意考虑的nums的区间是[lo,hi)，不包含hi点。同时target在nums中不存在时，会返回最适合插入的负位置(从-1开始计数)，target在nums中存在时，会返回索引位置(从0开始计数)。

快速排序(QuickSort)

很多优秀的排序算法都是基于快速排序，也是分治法的思路。

快速排序基本思路是，先确定一个数值点在排序之后的顺序，即把小于该数值点的值都放在该点前面，把大于该点的值都放在该点后面，这样该点的位置就已经固定了，同时就把一个大问题分成两个小问题，我们只需分别排序该数值点前后的数据，其过程也是先确定单个数值点的位置，不断递归。也就是说，快速排序每次迭代只确定一个值的位置。

伪代码表示如下，注意直接改变的原数组：

// java
Int Partition(int[] nums, int lo, int hi)
    x = nums[lo]    // 选定一个数值点，默认选第一个
    i = lo   // i最终会记录x应在的位置，i之前是小于x的数，i之后是大于x的数
    for(int j = lo+1, j <= hi, j++)
        if (nums[j]<x)
            i = i + 1
            nums[i] <-> nums[j]   // 交换i和j的位置，注意原来i位置存的是大于x的数，或者i和j都指向一个位置
                                  // 交换后，i位置存储目前最后一个小于x的值
    nums[lo] <-> nums[i]  // 交换lo和i的位置，至此，x找到了其在排序后数组中的位置，前面全是小于x的数，后面全是大于x的数
    return i

Void QuickSort(int[] nums, int start, int end)
    if start < end
        r = Parition(nums, start, end)
        QuickSort(nums, start, r-1)
        QuickSort(nums, r+1, end)

Partition的过程其时间复杂度是 $\Theta(n)$ ，如果原始数组是正序或倒叙排列，这是最坏情况，递归关系式是 $T(n)=T(1)+T(n-1)+\Theta(n)$ ，此时时间复杂度是 $O(n^{2})$ ；如果快速排序每次都可以把一个问题平分成两个子问题，这是最好情况，递归关系式是 $T(n)=2T(\frac{n}{2})+\Theta(n)$ ，时间复杂度是 $O (n l o g n)$ 。

为了解决出现最坏情况的问题，比较常用的方法是利用随机化技术，上面的代码我们每次都确定数组第一个点的位置，我们利用随机化技术，随机选择一个点确定他的位置，在一定程度上解决了最坏情况的问题。

# python3
import random

def quicksort(nums, l, r):
    if l >= r:
        return

    # 随机选择一个点排序
    rand = random.randint(l,r)
    tmp = nums[rand]
    nums[rand] = nums[l]
    nums[l] = tmp

    i = l + 1
    ii = l + 1
    while(i <= r):
        if nums[i] < nums[l]:
            tmp = nums[i]
            nums[i] = nums[ii]
            nums[ii] = tmp
            ii += 1
        i += 1
    tmp = nums[ii-1]
    nums[ii-1] = nums[l]
    nums[l] = tmp
    
    quicksort(nums, l, ii-2)
    quicksort(nums, ii, r)

原文链接：https://blog.csdn.net/Leon_winter/article/details/94456585