二、查找算法 查找检索:在一组数据中找出满足某秈冬/y据的过程 ■线性查找法 如果a1符合查找 件,则找到并 从第一个元素起 查找;否则 如果此时仍然没有 了前面的步骤 找到,返回未找到 下去 信息并停止 条件 条件 条件
二、查找算法 ◼ 线性查找法 a0 a1 ….. ai-1 ai ai+1 … aN-1 条件 从第一个元素起逐个元素进行比较 查找/检索：在一组数据中找出满足某种条件的数据的过程 如果ai-1符合查找 条件，则找到并 停止查找；否则 按照前面的步骤 继续下去。 条件 条件
二、查找算法 查找检索:在一组数据中找出满足某种条件的数据的过程 ■线性查找法 口在n个数据中进行线性查找,复杂度:O(n)
二、查找算法 ◼ 线性查找法 在n个数据中进行线性查找，复杂度：O(n) 查找/检索：在一组数据中找出满足某种条件的数据的过程
二、查找算法 查找检索:在一组数据中找出满足某种条件的数据的过程 二分查找法 线性查找要逐个比较表中元素。当表中元素非常多时,顺序查找 的效率是很低的。二分查找在速度方面有所改进,但是只适用于 已排好序的数组 输23 7910 16 入 查110W middle high 11 low middle Flag 11 low middle “找到11
二、查找算法 ◼ 二分查找法 查找/检索：在一组数据中找出满足某种条件的数据的过程 线性查找要逐个比较表中元素。当表中元素非常多时，顺序查找 的效率是很低的。二分查找在速度方面有所改进，但是只适用于 已排好序的数组。 low middle high 11 low 11 middle low middle 11 输 入 2 3 5 7 9 10 11 16 查11 Flag 0 查11 Flag 1 “找到11
二、查找算法 查找检索:在一组数据中找出满足某种条件的数据的过程 二分查找法 线性查找要逐个比较表中元素。当表中元素非常多时,顺序查找 的效率是很低的。二分查找在速度方面有所改进,但是只适用于 已排好序的数组 输入 2 3 5 9 16 low middle high 查4 middle high Flag 4 0 low igh middle 4 “未找到4
二、查找算法 ◼ 二分查找法 查找/检索：在一组数据中找出满足某种条件的数据的过程 线性查找要逐个比较表中元素。当表中元素非常多时，顺序查找 的效率是很低的。二分查找在速度方面有所改进，但是只适用于 已排好序的数组。 输 入 2 3 5 7 9 10 11 16 low middle high 4 high 4 middle low middle 4 high 查4 Flag 0 “未找到4
/ Example: binary search * 要求在一组整数中査找一个值* int search(int all, int N, int key int low=0, high=N-1, middle, i while(low < high) middle =(low high)/2 if (key== a[middle) return middle else if (key <a[middled high middle-1: /*lower half */ ese low= middle 1; / upper half * return←1:/ not found*
/* Example: binary search */ /* 要求在一组整数中查找一个值*/ int search(int a[], int N, int key) { int low = 0, high = N-1, middle, i; while (low <= high) { middle = (low + high) / 2; if (key == a[middle]) return middle; else if (key <a[middle]) high = middle - 1; /* lower half */ else low = middle + 1; /* upper half */ } return -1; /* not found */ }