查找算法总结

顺序查找

基本思想

int search(int a[], int n, int key){
    for (int i = 0; i < n; i++)
        if (a[i] == key)
            return i + 1;
    return 0;
}

经典查找——设置哨兵

int search(int a[], int n, int key){
    a[0] = key;
    for (int i = n; a[i] != key; i--) // 从后往前查找
        return i; 
}

二分查找

特征：

• 待查表是有序表
• 非链表结构

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作
是r = mid或者l = mid + 1;，计算mid时不需要加1。
模板：

int bearch_1(int l, int r)
{
  while (l < r)
  {
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1; 
  }
  return l;
}

版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，
其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

python

def binary_search(list, item):
  # low and high keep track of which part of the list you'll search in.
  low = 0
  high = len(list) - 1

  # While you haven't narrowed it down to one element ...
  while low <= high:
    # ... check the middle element
    mid = (low + high) // 2
    guess = list[mid]
    # Found the item.
    if guess == item:
      return mid
    # The guess was too high.
    if guess > item:
      high = mid - 1
    # The guess was too low.
    else:
      low = mid + 1

  # Item doesn't exist
  return None

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1

# 'None' means nil in Python. We use to indicate that the item wasn't found.
print(binary_search(my_list, -1)) # => None

思考过程：

一般写二分的思考顺序是这样的：首先通过题目背景和check(mid)函数的逻辑，判断答案落在左半区间还是右半区间。
左右半区间的划分方式一共有两种：

• 中点mid属于左半区间，则左半区间是[l, mid]，右半区间是[mid+1, r]，更新方式是r = mid;或者 l = mid + 1;，此时用第一个模板；
• 中点mid属于右半区间，则左半区间是[l, mid-1]，右半区间是[mid, r]，更新方式是r = mid - 1;或者 l = mid;，此时用第二个模板；

动态查找——二叉排序树（left < root < right）

特征：插入或删除较为频繁

查找

template <class T>
Node<T>* search(Node<T>* root, T key){
    if (!root) return nullptr;
    if (root -> val == key) return root;
    else if (root -> val > key) return search(root -> left, key);
    else return search(root -> right, key);
}

插入

//         30
        //      /      \
        //     20      40
        //    /  \    /
        //   10  25  35
void insertBST(Node<int>* root, Node<int>* s){
    if (!root) root = s;
    else if (s -> val < root -> val)
        insertBST(root -> left, s);
    else 
        insertBST(root -> right, s);
}

二叉排序树建立过程

void creat(Node<int>* root, int r[], int n){
    for (int i = 0; i < n; i++){
        auto s = new Node<int>(-1);
        s -> val = r[i];
        s -> left = s -> right = nullptr;
        insertBST(root, s);
    }
}

删除

删除之后仍然要保证有序性：

1. 删除叶子结点：直接删除
2. 结点只有左（右）子树：将结点删除并将其左（右）子树连接在父结点上
3. 结点左右都有：查找该结点的前驱，将待删除结点用前驱结点覆盖，并删除其前驱节点。

template <class T>
void Delete(Node<T>* &R){
    Node<T> *q, *s; // s是R的前驱，q是s的双亲
    if (R -> left == nullptr) {
        q = R;
        R = R -> right;
        delete R;
    }
    else if (R -> right == nullptr) {
        q = R;
        R = R -> left;
         delete R;
    }
    q = R;
    s = R -> left;
    while (s ->rignt != nullptr) 
        q = s, s = s -> right;
    R -> val = s -> val
    if (q != R)
        q -> right = s -> left;
    else 
        R -> left = s -> left;
    d  elete s;
}