【数据结构】[第七章 查找][自用]

1基本概念

（1）

（2）静态与动态查找表

（3）查找长度 与 平均查找长度（成功与失败）

2 普通查找

2.1 顺序查找

（1）代码：

static int sequentialSearch(vector<int> arr, int target){    
    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] == target) {
            return i; // 如果找到目标值，则返回索引
        }
    }
    return -1; // 如果未找到目标值，则返回 -1    
}
 
//王道代码：
static int sequentialSearch(vector<int> arr, int target){    
    for (int i = 0; i < arr.size()&&arr[i] != target; ++i);
    return i==arr.size()?-1:i; // 如果未找到目标值，则返回 -1    
}

（2）查找效率分析：

（3）改进：

1. 查找概率相等：
2. 查找概率不相等：所以要根据情况来选择优化方式。

2.2 折半查找

（1）代码：

//二分查找函数
static int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
 
    while (left <= right) {
        int mid = left + (right - left) / 2; // 计算中间位置
 
        // 如果目标值等于中间元素，则返回中间位置
        if (arr[mid] == target) {
            return mid;
        }
        // 如果目标值小于中间元素，则在左侧继续查找
        else if (arr[mid] > target) {
            right = mid - 1;
        }
        // 如果目标值大于中间元素，则在右侧继续查找
        else {
            left = mid + 1;
        }
    }
 
    // 如果未找到目标值，则返回 -1
    return -1;
}

（2）过程：

• 注意：折半查找，仅仅适用于有序的顺序表。不适用于链表，因为链表不具备随机存取这一特性。

（3）查找效率：

（4）折半查找判定树的构造：

下图中，数字只代表顺序，不代表值。

（5）与顺序查找相比&#x