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)改进:
- 查找概率相等:
- 查找概率不相等:所以要根据情况来选择优化方式。
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