1.3 Search & Sort

Search Algorithms

搜算算法，或者说查找算法，是初级算法的“地基”。

Binary Search

二分查找，又是搜索算法的“地基”。非常经典！

Prerequisites: input is sorted.

算法：每次切一半，根据中值判断需要结果在左边还是右边。（这里迭代或者递归的实现差不多）

时间复杂度：O(logn)，2为底的对数

Iterative

int binary_search(int A[], int key, int imin, int imax)
{
    while (imin <= imax)
    {
        int imid = midpoint(imin, imax); // calculate the midpoint for roughly equal partition
        if (A[imid] == key)
            return imid;
        else if (A[imid] < key)
            imin = imid + 1; // change min index to search upper subarray
        else
            imax = imid - 1; // change max index to search lower subarray
    }
    return KEY_NOT_FOUND;
}

Recursive

int binary_search(int A[], int key, int imin, int imax)
{
    if (imax < imin) // test if array is empty
        return KEY_NOT_FOUND;
    else {
        int imid = midpoint(imin, imax); // calculate midpoint to cut set in half
        if (A[imid] > key) // key is in lower subset
            return binary_search(A, key, imin, imid - 1);
        else if (A[imid] < key) // key is in upper subset
            return binary_search(A, key, imid + 1, imax);
        else // key has been found
            return imid;
    }
}

关键点1：mid节点的选取

• （偶数个情况下）选取中间靠左的节点：mid = (left + right) / 2;​
• （偶数个情况下）选取中间靠右的节点：mid = (left + right + 1) / 2;
• 注：奇数个情况下，两种方法算出来的节点都是中位数节点，因为整除会向下取整

关键点2：满足条件，循环跳出的情况

• 找到 target
• 左右节点互相穿越

（例子体会：LC 852 山脉数组的峰顶索引）https://leetcode.cn/problems/peak-index-in-a-mountain-array/

Example

Problem: 查找第一个残次品

• You are developing a product. It has n versions 1-n. It is broken at some point. You want to find out the first bad one, which causes all the following ones to be bad.
• You are given an API bool isBadVersion(version) which will return whether version is bad.
• Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution:

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

// last case: start(good), end(bad)
//            mid = start
//            start++ -> end
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1, end = n;
        while (start < end) {
            int mid = start + (end-start) / 2;
            if (!isBadVersion(mid)) start = mid + 1;
            else end = mid;
        }
        return start;
    }
}

Sorting Algorithms

Quick Sort

快排算法：思想类似二分查找

• 也是在中值处切一刀，然后移动元素，保证左半区的小于中值，右半区的大于中值。
• 然后左右半区重复该过程。可以理解为建立一颗二分查找树。

时间复杂度分析：平均是O(nlogn)

• 二分的时间复杂度为平均O(logn)
• 移动元素的时间复杂度为O(n)

Choose a pivot and put elements on left or right of it, do it recursively

• Choose a pivot value. We take the value of the middle element as pivot value. (it can be any value even not in the array)
• Partition. Rearrange elements in such a way that:
• All elements lesser than the pivot go to the left part of the array
• All elements greater than the pivot go to the right part of the array.
• Values equal to the pivot can stay in any part of the array.
• Sort both parts. Apply quicksort algorithm recursively to the left and the right parts. （注：用递归写起来比较简便）

int partition(int arr[], int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];

    while (i <= j) {
        while (arr[i] < pivot)
        i++;
        while (arr[j] > pivot)
        j--;
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

    return i;
}

void quickSort(int arr[], int left, int right) {
    int index = partition(arr, left, right);
    if (left < index - 1)
        quickSort(arr, left, index - 1);
    if (index < right)
        quickSort(arr, index, right);
}

QuickSort

Bubble Sort

冒泡排序，算法

• Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them. （注意：每次循环，最大的数必然沉淀到最后去）
• If at least one swap has been done, repeat step 1.

Time Complexity: O(n^2)

public void bubbleSort(int[] arr) {
    boolean swapped = true;
    int j = 0;
    int tmp;
    while (swapped) {
        swapped = false;
        j++;
        for (int i = 0; i < arr.length - j; i++) {
            if (arr[i] > arr[i + 1]) {
                tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = true;
            }
        }
    }
}

BubbleSort