search-algorithm.md

查找算法

**查找定义：**根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找算法分类：

• 静态查找和动态查找**：**静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
• 无序查找和有序查找。
  • 无序查找：被查找数列有序无序均可；
  • 有序查找：被查找数列必须为有序数列。

**平均查找长度（Average Search Length，ASL）：**需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。对于含有n个数据元素的查找表，查找成功的平均查找长度为： $$ASL = P_i\times C_i$$ 的和。

• $$P_i$$ ：查找表中第 $$i$$ 个数据元素的概率。
• $$C_i$$ ：找到第 $$i$$ 个数据元素时已经比较过的次数。

🖋 1、顺序查找

**顺序查找适合于存储结构为顺序存储或链接存储的线性表。**顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

🖋 2、二分查找

**元素必须是有序的，如果是无序的则要先进行排序操作。**二分查找也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为 $$log2(n+1)$$ ，且期望时间复杂度为 $$O(log2n)$$ ；

注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right){
        int mid = (left + right) >> 1;
        if(nums[mid] == target)
            return mid;
        if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return -1;
}