折半查找法例题

折半查找⼀.题⽬要求·题⽬输⼊n(n<100)个有序正数，请⽤折半查找算法，查找x在其中的位置。

·测试输⼊:5 1,2,3,4,5 2输出:2注：测试集合中，x数⼀定在正数数组中。

即不⽤处理错误逻辑。

⼆.题⽬分析输⼊的第⼀个数是数的个数，第⼆组数是⼀组有序的数，即不需要⾃⼰排序，第三个数则是要查找的数。

折半查找，也称⼆分查找，即利⽤⼆分法进⾏查找。

在某些情况下相⽐于顺序查找，使⽤折半查找算法的效率更⾼。

但是该算法的使⽤的前提是静态查找表中的数据必须是有序的。

三.代码实现#include <stdio.h>int main() {int n, i;int series[100];int t;int right, left, middle;//输⼊scanf_s("%d", &n);for (i = 0; i < n; i++) {scanf_s("%d,", &series[i]);}scanf_s("%d", &t);//初始化left = 0;right = n - 1;middle = (n - 1) / 2;//⼆分法查找while (series[middle] != t) {if (series[middle] < t) right = middle;else left = middle;middle = (left + right) / 2;}printf("%d", middle);return 0;}好吧，上⾯的代码还是运⾏不了（似曾相识）。

调试的时候发现数组元素的输⼊没有成功，但是没有找到错误的原因。

然后我在⽹上找到了⼩刘同学分享的代码。

我这⾥也展⽰⼀下他的源码。

#include <stdio.h>int main(){int num[100];int a,b,flag,i=0;scanf("%d",&a);for(i=0;i<a;i++){scanf("%d,",&num[i]);}scanf("%d",&b);int left=0,right=a-1;while(left<=right){flag = (left+right)/2;if(b==num[flag]){printf("%d",flag+1);break;}if(num[flag] > b)right = flag-1;else if(num[flag] < b)left = flag+1;}}我对⽐了⼀下，除了⼆分查找的实现部分，前⾯的不~TM~是⼀样的吗。

if(ST.R[i].key==key) return i; //从后往前找return 0;}//Search _Seq 算法7.1在查找过程中每步都要检测整个表是否查找完毕，即每步都要有循环变量是否满足条件i >=1的检测。

改进这个程序，可以免去这个检测过程。

改进方法是查找之前先对ST.R[0]的关键字赋值key ，在此，ST.R[0]起到了监视哨的作用，如算法7.2所示。

算法7.2 设置监视哨的顺序查找【算法描述】int Search _Seq(SSTable ST,KeyType key){//在顺序表ST 中顺序查找其关键字等于key 的数据元素。

若找到，则函数值为//该元素在表中的位置，否则为0ST.R[0].key=key; //“哨兵”for(i=ST.length;ST.R[i].key!=key;--i); //从后往前找retutn i;}//Search _Seq 【算法分析】算法7.2仅是一个程序设计技巧上的改进，即通过设置监视哨，免去查找过程中每一步都要检测整个表是否查找完毕。

然而实践证明，这个改进能使顺序查找在ST.length ≥1000时，进行一次查找所需的平均时间几乎减少一半。

当然，监视哨也可设在高下标处。

算法7.2和算法7.1的时间复杂度一样，在第2章已经做过分析，即 1112n i n ASL i n =+==∑ 算法7.2的时间复杂度为O （n ）。

顺序查找的优点是：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可应用。

其缺点是：平均查找长度较大，查找效率较低，所以当n 很大时，不宜采用顺序查找。

7.2.2 折半查找折半查找（Binary Search ）也称二分查找，它是一种效率较高的查找方法。

但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

在下面及后续的讨论中，均假设有序表是递增有序的。

折半查找（Binary Search）是一种高效的查找算法，适用于已排序的数组。

其基本思想是每次将待查找的元素与数组中间元素进行比较，根据比较结果缩小查找范围，直到找到目标元素或查找范围为空。

下面是一个折半查找的例题：假设有一个已排序的整数数组`arr = [1, 3, 5, 7, 9]`，请编写一个折半查找算法，查找元素`target = 5`在数组中的位置。

解析：1. 初始化左指针`left`和右指针`right`，分别指向数组的第一个元素和最后一个元素。

2. 当`left <= right`时，执行以下操作：a. 计算中间位置`mid = (left + right) // 2`。

b. 如果`arr[mid] == target`，则返回`mid`。

c. 如果`arr[mid] < target`，则将左指针`left`更新为`mid + 1`。

d. 如果`arr[mid] > target`，则将右指针`right`更新为`mid - 1`。

3. 如果遍历完数组仍未找到目标元素，则返回-1表示未找到。

代码实现（Python）：```pythondef binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1arr = [1, 3, 5, 7, 9]target = 5result = binary_search(arr, target)print(result) # 输出：2```。

折半查找算法（Python版）⽬录介绍⼆分查找也称折半查找（Binary Search），它是⼀种效率较⾼的查找⽅法。

但是，折半查找要求线性表必须采⽤顺序存储结构，⽽且表中元素按关键字有序排列。

前提必须待查找的序列有序时间复杂度O(log2n)原理1）确定该期间的中间位置K2）将查找的值t与array[k]⽐较，若相等，查找成功返回此位置；否则确定新的查找区域，继续⼆分查找。

3）区域确定过程：若array[k]>t，由于数组有序，所以array[k,k+1,……,high]>t；故新的区间为array[low, ..., K-1]；反之，若array[k]<t对应查找区间为array[k+1, ..., high]#!/usr/bin/env python# -*- coding: utf-8 -*-# @Date : 2020-07-10# @Author : 流柯# @desc : ⼆分查找算法，python版def serach(array, t):array.sort() #排序，保证列表是有序的low = 0height = len(array) - 1while low <= height:k = (low + height) // 2if array[k] < t:low = k + 1elif array[k] > t:height = k - 1else:return k #找到后返回位置return -1 #找不到返回-1array = [1, 3, 5, 7, 9, 6, 8, 0]print(serach(array, 5))End。

实现顺序查找和折半查找的算法顺序查找和折半查找（也称为二分查找）是两种常见的查找算法。

以下是它们的Python实现：1. 顺序查找：```pythondef sequential_search(list, item):pos = 0found = Falsewhile pos < len(list) and not found:if list[pos] == item:found = Trueelse:pos = pos+1return found```这个函数会检查列表中的每个元素，直到找到匹配的元素或者遍历完整个列表。

如果找到匹配的元素，函数会返回True，否则返回False。

2. 折半查找：```pythondef binary_search(list, item):low = 0high = len(list) - 1mid = 0found = Falsewhile low <= high and not found:mid = (high + low) // 2if list[mid] == item:found = Trueelif list[mid] < item:low = mid + 1else:high = mid - 1return found```这个函数使用二分查找算法，每次比较列表中间的元素和目标元素。

如果中间元素等于目标元素，函数返回True。

如果中间元素小于目标元素，函数在列表的右半部分继续查找。

如果中间元素大于目标元素，函数在列表的左半部分继续查找。

如果函数遍历完整个列表都没有找到目标元素，那么返回False。

折半查找折半查找1. 算法思想2. 算法实现3. 查找判定树4. 折半查找效率折半查找的算法思想折半查找，⼜称“⼆分查找”，仅适⽤于有序的顺序表33>mid，往右查右指针到⼀个位置就-1，左指针到⼀个位置就+1low>high，查找失败折半查找的实现typedef struct{ElemType *elem;int TableLen;}SSTable;//折半查找（升序）int Binary_Search(SSTable L,ElemType key){int low = 0,high = L.TableLen-1,mid;while(low<=high){mid = (low+high)/2; //取中间位置if(L.elem[mid] == key)return mid; //查找成功则返回所在位置else if(L.elem(mid)>key)high = mid -1; //从前半部分继续查找elselow = mid +1; //从后半部分继续查找}return -1; //查找失败，返回-1}顺序表拥有随机访问的特性，链表没有查找效率复分析查找判定树的构造如果当前low和high之间有奇数个元素，则mid分隔后，左右两个部分元素个数相等如果当前low和high之间有偶数个元素，则mid分隔后，左半部分⽐右半部分少⼀个元素折半查找的判定树中，若 mid=向下取整(low+high)/2，对于任何⼀个结点，必有：右⼦树结点-左⼦树结点=0或1⾃⼰过⼀遍顺序，1个元素，2个元素，。

折半查找的判定树⼀定是平衡⼆叉树因此，元素个数为n时树⾼h=⌈log2(n+1)⌉计算完全⼆叉树也相同满⾜⼆叉排序树的定义失败节点：n+1个，等于成功结点的空链域数量知识回顾⼤部分情况下折半查找速度都⽐顺序查找快。

但是不⼀定哦从上去整，不⼀样哦，左边的⽐较多Processing math: 100%。

c语言使用折半查找法的示例代码C语言使用折半查找法的示例代码1. 引言折半查找法（Binary Search）是一种常用的查找算法，它通过将有序数组分成两半的方式快速定位要查找的元素。

在本文中，我们将探讨C语言中如何实现折半查找的算法，并提供一个示例代码来演示其实际应用。

2. 算法思路折半查找法的基本思路是不断将查找范围缩小为一半，直到找到目标元素或者确认目标元素不存在。

以下是该算法的详细步骤：- 确定查找范围的起始位置（通常是数组的起始位置）和结束位置（通常是数组的末尾位置）。

- 计算查找范围的中间位置，并取得该位置上的元素。

- 如果中间元素等于目标元素，则查找成功，并返回该元素的位置。

- 如果中间元素大于目标元素，则将查找范围缩小为数组起始位置到中间位置-1的一半。

- 如果中间元素小于目标元素，则将查找范围缩小为中间位置+1到数组末尾位置的一半。

- 重复以上步骤，直到找到目标元素或者确认目标元素不存在。

3. 示例代码下面是一个使用C语言实现折半查找法的示例代码：```c#include <stdio.h>int binarySearch(int arr[], int low, int high, int target) { while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == target) {return mid;}else if (arr[mid] < target) {low = mid + 1;}else {high = mid - 1;}}return -1; // 目标元素不存在的情况int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13};int size = sizeof(arr) / sizeof(arr[0]);int target = 9;int result = binarySearch(arr, 0, size - 1, target);if (result == -1) {printf("目标元素不存在\n");}else {printf("目标元素在数组中的位置为：%d\n", result);}return 0;}```4. 代码解析上述示例代码中，我们首先定义了一个名为`binarySearch`的函数，该函数接受一个有序数组`arr`、查找范围的起始位置`low`、结束位置`high`和目标元素`target`作为参数。

第9章查找【例9-1】有序表按关键字排列如下：7，14，18，21，23，29，31，35，38，42，46，49，52，在表中查找关键字为14和22的数据元素，并画出折半查找过程的判定树。

解：折半查找的过程描述如下：①low=1；high=length；//设置初始区间②当low>high时，返回查找失败信息//表空，查找失败③low≤high，mid=(low+high)/2; //取中点a. 若kx<tbl.elem[mid].key，high=mid-1；转②//查找在左半区进行b. 若kx>tbl.elem[mid].key，low=mid+1；转②//查找在右半区进行c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置//查找成功●查找关键字为14的过程如下：low=1 ①设置初始区间high=13───────────────────────────↑②表空测试，非空；mid=7 ③得到中点，比较测试为a情形↑↑low=1 high=6 high=mid-1，调整到左半区────────────────────────────↑②表空测试，非空；mid=3 ③得到中点，比较测试为a情形↑↑low=1 high=2 high=mid-1，调整到左半区────────────────────────────↑②表空测试，非空；mid=1 ③得到中点，比较测试为b情形↑↑low=2 high=2 low=mid+1，调整到右半区────────────────────────────↑②表空测试，非空；mid=2 ③得到中点，比较测试为c情形查找成功，返回找到的数据元素位置为2●查找关键字为22的过程如下：low=1 ①设置初始区间high=13────────────────────────────↑②表空测试，非空；mid=7 ③得到中点，比较测试为a情形↑↑low=1 high=6 high=mid-1，调整到左半区───────────────────────────↑②表空测试，非空；mid=3 ③得到中点，比较测试为b情形↑ ↑low=4 high=6 low=mid+1，调整到右半区────────────────────────────↑ ②表空测试，非空；mid=5 ③得到中点，比较测试为a 情形↑↑low=4 high=4 high=mid-1，调整到左半区────────────────────────────↑ ②表空测试，非空；mid=4 ③得到中点，比较测试为b 情形↑ ↑high=4 low=5 low=mid+1，调整到右半区────────────────────────────②表空测试，为空；查找失败，返回查找失败信息为0查找过程的判定树如图7-1所示。

降序存储的一组整数(10个),任意输入一个数,用折半查找法找出该数的
位置。

折半查找法是一种有效的查找算法，能够实现快速且精准的查找指定元素的位置。

它的基本规则就是：将查找区间的中间元素的值和要查找的关键字比较，如果相等，则查找成功；若小于要查找的关键字，则将查找区间缩小为原来的左半部分；若大于关键字，则将查找区间缩小为原来的右半部分。

这种方式可使查找区间每次减少二分之一，同时也将查找元素的位置困难度降低，从而达到较高效率并快速找到元素，而无需遍历整个数组。

假设现在我们有一个降序排列的数组（10个元素），任意输入一个数，我们可以使用折半查找法来快速查找到该数字在数组中的位置。

首先，我们需要找到数组中间的位置，即索引号为5，当输入的数小于或等
于数组索引号5的元素时，我们可以将查找区间缩小为原来数组的左半部分，否则将查找区间缩小为原来数组的右半部分。

然后，重复上述操作，直到找到要查找的数字，从而确定数字在数组中的位置。

由于折半查找法每次剔除大量无效的查找元素，因此经过几次查找可以较快的找到目标数字的位置，大大提高了查找的工作效率。

C语言程序设计100例之（21）：折半查找例21 折半查找问题描述顺序查找是一种最简单和最基本的检索方法。

其基本思想是：从检索表的一端（如表中第一个记录或最后一个记录）开始，逐个进行记录的关键字和给定值的比较。

若某个记录的关键字和给定值比较相等，则查找成功；否则，若直至检索表的另一端（如最后一个记录或第一个记录），其关键字和给定值比较都不等，则表明表中没有待查记录，查找不成功。

顺序查找可以写成一个简单的一重循环，循环中依次将检索表（不妨设为数组a）中的元素与给定值比较，若相等，用break退出循环。

算法描述为：for (i=0; i< n;i++)if (a[i]==x) break;这样，循环结束后，若循环控制变量i小于数组元素个数n，则查找成功；否则，查找失败。

顺序查找实现简单，但效率不高。

当待查找序列有序时，即各检索表中元素的次序是按其记录的关键字值的大小顺序存储的。

此时采用折半查找会大幅提高查找效率。

折半查找的基本思想是先确定待查数据的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

具体做法是：先取数组中间位置的数据元素与给定值比较。

若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分（或后半部分），然后在新的查找范围内进行同样的查找。

如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。

因此，折半查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。

输入一个整数，在给定的有序数组中查找该整数是否存在，若存在，给出其数组的下标；若不存在，输出查找不成功信息。

输入格式第一行是一个正整数N (1 ≤N ≤100000)，代表数组中元素的个数。

第二行有N个整数，这N个整数从小到大排列好了。

第三行是一个整数M，代表待查找元素的个数。

接下来的M行，每行有一个整数x，表示每个待查找的元素。

折半查找例题折半查找，也称为二分查找，是一种用于在有序数组中查找指定元素的算法。

这种查找算法通过将数组分成两个部分进行比较，从而将查找范围逐步减半，直到找到目标元素或者确定目标元素不存在。

下面将为您介绍一个使用折半查找算法解决的例题。

假设有一个包含1000个元素的有序数组，其中包含了1到1000之间的所有整数（包括1和1000），请编写程序来查找数组中某个指定的整数x，并输出其在数组中的索引位置。

为了实现这一目标，我们可以使用折半查找算法。

首先，我们需要定义一个函数binary_search，用于执行折半查找。

该函数将接收三个参数：一个有序数组arr，数组的起始位置left和终止位置right，以及目标整数x。

接下来，我们可以编写折半查找的具体实现代码。

代码如下：```pythondef binary_search(arr, left, right, x):if right >= left:mid = left + (right - left) // 2if arr[mid] == x:return midelif arr[mid] > x:return binary_search(arr, left, mid - 1, x)else:return binary_search(arr, mid + 1, right, x)else:return -1# 测试代码arr = [i for i in range(1, 1001)] # 创建包含1到1000之间所有整数的数组x = 543 # 指定要查找的整数result = binary_search(arr, 0, len(arr)-1, x)if result != -1:print("目标整数在数组中的索引位置为:", result)else:print("目标整数在数组中不存在。

")```通过以上代码，我们可以得到结果：目标整数在数组中的索引位置为: 542。