查找算法（未完待续......最近确实忙，有时间一定续上）

一、静态查找：只查找给定的值，不做其他任何的操作，不改变表结构和数据元素

1.查找某特定的关键字是否在表中（判断性查找）
2.检索某特定关键字的数据元素的各种属性（检索性查找）

（一）顺序查找（待查找数据无序）

顺序查找也叫线性查找，它的查找过程：从表中的第一个（最后一个）数据元素开始，逐个将给定值和数据元素的属性进行对比，如果两个值相等，查找成功，直到查找到最后所有数据元素都不相等，则查找失败。 示例代码如下：

 /**
 顺序查找（正序）

 @param a 待查找数组
 @param n 数组中元素个数
 @param key 给定值
 @return 目标数据元素的在数组的下标，若为0则查找失败
 */
int seq_search(int *a, int n, int key) {
    for (int i = 1; i < n; ++i) {
        if (key == a[i]) {
            return i;
        }
    }
    return 0;
}
                                  程序1.1.1

程序1.1.1是一个简单的顺序查找示例，这个实现是有改进空间的，我们可以看到每次for循环都要进行一次防止数组越界的比较 i < n，这是一个可优化点，我们可以在查找方向的末端设置一个哨兵，这个哨兵是给定值，倘若程序在查找过程中已经找到，那么返回的值为目标数据元素在数组中的下标，否则，为我们设定的哨兵在数组的下标

/**
 顺序查找（正序）
 
 @param a 待查找数组
 @param n 数组中元素个数
 @param key 给定值
 @return 目标数据元素的数组下标，若为n则查找失败
 */
int seq_search2(int *a, int n, int key) {
    int i = 0;
    a[n] = key;
    while (a[i] != key) {
        i++;
    }
    return i;
}
                                  程序1.1.2

顺序查找的时间复杂度：

• 在查找成功的情况下：
  目标元素在第一个位置，循环一次查找成功，时间复杂度为O(1)
  目标元素在最后一个位置，循环n次查找成功，时间复杂度为O(n)
• 失败的情况下:
  程序1.1.1需要循环n次，时间复杂度为O(n)
  程序1.1.2需要循环n+1次，时间复杂度为O(n)

ASL = ∑ Pi * Ci（i = 1， 2， 3 .... n, 即将所有位置查找的概率与查找到该位置比较的次数的乘积进行累和）
Pi：每个位置上的查获找成功的概率是相同的为 1/n
Ci：查找成功的次数为（1 + 2 + 3 + ......+ n ）= n * (n + 1) / 2
ASL：平均查找长度为：1/n * { n * (n + 1) / 2} = (n + 1) / 2

因此顺序查找的时间复杂度为O(n)

（二）折半查找（待查找数据有序）

折半查找也叫二分查找使用折半查找的前提是带查找的数据是有序的（从小到大），它的查找过程：取待查找数据的中间的一个数据元素与给定值行比较

• 如果两者相等，查找成功
• 如果所取数据元素比给定值大，则在中间元素的左侧继续重复查找过程，直到查找成功或者失败
• 如果所取数据元素比给定值小，则在中间元素的右侧继续重复查找过程，直到查找成功或者失败

/**
 折半查找
 
 @param a 待查找数组
 @param n 数组中元素个数
 @param key 给定值
 @return 目标数据元素的数组下标，若为0则查找失败
 */
int binary_search(int *a, int n, int key) {
    
    //数组的第一个元素的下标
    int low = 0;
    
    //数组的最后一个元素的下标（数组下标从0开始，n为长度，因此最后一元素的下标为0）
    int height = n - 1;
    
    //计算的出数组中间的数据元素的下标
    int mid = (low + height) / 2;
    
    //只要待查找的区域的首部和尾部不相等
    //若是相等，意味着，收尾相接，只有一个元素
    while (low <= height) {
        
        //给定值key和数组中间的数据元素相等
        if (key == a[mid]) {
            
            //查找成功
            return a[mid];
            
        //给定值key比中间的数据元素大，则要继续下一次查找
        } else if (key > a[mid]) {
            //下一次查找的区域改变为 中间值右侧到数组末尾
            //此时需要改变low的值，进而改变mid的值
            //low = mid + 1是因为，mid已经取过了，比较过了
            low = mid + 1;
            
        //给定值key比中间的数据元素小，则要继续下一次查找
        } else {
            //下一次查找的区域改变为 中间值左侧到数组末尾
            //此时需要改变height的值，进而改变mid的值
            //height = mid - 1是因为，mid已经取过了，比较过了
            height = mid - 1;
        }
        
        //每一趟不成的查找都要重新计算mid的值，从而进行下一次的折半查找
        mid = (low + height) / 2;
    }
    
    return 0;
}

二、动态查找：给定值，在查找过程中插入此数据元素不存在则插入给定值的数据元素，或者，删除给定值所对应的数据元素

1.查找时插入数据元素
2.查找时删除数据元素