第6章 查找运算

目录6.1查找概述6.2顺序查找6.3二分查找6.4STL中的查找函数6.1查找概述查找是计算机编程中最基本、最常用的操作之一，我们每天都在使用它，比如在通讯录里找联系人，在文件系统中找文件。在本章中，我们将学习几种经典的查找算法，包括顺序查找和二分查找，并了解如何利用C++标准库中的查找函数来提高编程效率。第6章查找定义：在大量信息中寻找特定元素的过程。基本定义常见算法：1.顺序查找2.二分查找3.插值查找4.哈希查找等常见算法分类：无序查找：数列无需有序（如顺序查找）。有序查找：数列必须有序（如二分查找）。算法分类6.1查找概述6.2.1顺序查找基础一、基本思想逐个比较数组元素与目标值，找到则返回索引，否则返回-1。二、性能分析•时间复杂度：O(n)•最好情况：1次比较•最坏情况：n次比较•平均情况：(n+1)/2次比较三、核心代码实现intSequenceSearch(inta[],intn,intkey){for(inti=0;i<n;i++)if(a[i]==key)returni;return-1;}监视哨技术核心思想在数组末尾添加一个等于目标值的“监视哨”，避免每次循环都检查数组是否越界，将两次判断合并为一次。操作步骤1.将目标值存入数组末尾。2.从数组头部开始查找，找到目标值即停止。3.判断位置，若是末尾则说明原数组无目标值。代码优化点在循环中只需判断元素是否相等，无需判断索引是否越界。从而减少了一半的比较次数，提高了查找效率。优化代码通过引入监视哨，我们将原本在循环中需要进行的“索引越界检查”和“目标值比较”这两个操作，简化为了单一的“目标值比较”。这种优化在数据量较大时能显著减少CPU的指令执行次数，从而提升算法效率。6.3.1二分查找概述一、基本思想利用分治思想，在有序数组中，通过不断将查找区间减半来快速定位目标值。二、适用条件待查找的数据序列必须是有序的（升序或降序）。三、查找步骤取中间位置元素与目标值比较；若相等则查找成功；若目标值更小，在左半区间继续查找；若更大，在右半区间继续查找；重复步骤，直到找到目标值或区间为空（查找失败）。图6-1二分查找过程示意图一、核心代码（C++实现）intBinSearch(inta[],intn,intkey){intleft=0,right=n-1;while(left<=right){intmid=(left+right)/2;if(a[mid]==key)

returnmid;elseif(a[mid]<key)

left=mid+1;else

right=mid-1;}return-1;}6.3.2二分查找程序（循环法）二、性能分析二分查找每次比较都将查找区间缩小一半，时间复杂度为O(logn)，在数据量较大时，查找效率远优于顺序查找（O(n)）。6.3.2二分查找程序（递归法）算法思想：递归法将查找问题分解为更小的子问题，直到规模缩小到可直接解决。代码简洁，但性能略逊于循环法，且存在栈溢出风险。intBinSearch(inta[],intleft,intright,intkey){if(left>right)return-1;//递归终止条件intmid=left+(right-left)/2;if(a[mid]==key)

returnmid;elseif(a[mid]<key)returnBinSearch(a,mid+1,right,key);elsereturnBinSearch(a,left,mid-1,key);}6.3.3查找左右边界1.问题描述在有序数组中存在重复元素时，需要查找目标值第一次出现（左边界）或最后一次出现（右边界）的位置。2.算法思路基于二分查找框架，当找到目标值时不立即返回。查找左边界时，收缩右边界继续向左搜索；查找右边界时，收缩左边界继续向右搜索。直到区间无效，最终确定边界位置。3.核心代码逻辑(查找左边界)intleft_bound(int[]nums,inttarget){...if(nums[mid]==target)

right=mid-1;...}6.4.1STL查找概述概述：C++标准模板库（STL）提供了丰富的查找函数，无需手动实现。binary_search功能：判断指定元素是否存在于有序区间中。返回值：存在返回true，否则返回false。存在性判断lower_bound功能：查找第一个大于等于目标值的元素。返回值：指向该元素的迭代器。查找下界upper_bound功能：查找第一个大于目标值的元素。返回值：指向该元素的迭代器。查找上界【功能描述】在有序区间内查找目标值是否存在。该函数不返回具体位置，仅判断存在性。【函数语法】

binary_search(first,last,value)【返回值】布尔值（bool）：找到返回true，未找到返回false。【示例代码】

vector<int>v={1,3,5,7,9};boolfound=binary_search(v.begin(),v.end(),5);//found=true6.4.2binary_search函数lower_bound函数：返回容器中第一个大于等于目标值的元素位置。upper_bound函数：返回容器中第一个大于目标值的元素位置。返回值类型：迭代器（对于普通数组则是指针），指向找到的边界位置。核心用途：在有序序列中高效查找元素的插入点或边界，时间复杂度为O(logn)。6.4.3lower_bound与upper_bound函数图6-4lower_bound与upper_bound返回值示意图课堂小结●顺序查找：简单直观，适用于无序数据，时间复杂度O(n)，可通过监