erfenchazhao
时间: 2024-04-09 22:32:53 浏览: 49
二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两部分,取中间值与要查找的值进行比较,如果中间值等于要查找的值,则查找成功;如果中间值大于要查找的值,则在数组左半部分继续查找;如果中间值小于要查找的值,则在数组右半部分继续查找。如此递归下去,直到找到要查找的值或者确定要查找的值不存在为止。
以下是 C 语言实现的二分查找代码示例:
```c
int binarySearch(int arr[], int n, int target)
{
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
```
其中,`arr[]`为要查找的有序数组,`n`为数组的长度,`target`为要查找的值。函数返回值为 `target` 在数组 `arr[]` 中的下标,如果不存在则返回 `-1`。
相关问题
#include<iostream> using namespace std; typedef int KeyType; typedef struct{ KeyType key; char name[30]; }ElemType; typedef struct{ ElemType *R; int length =0; }SSTable; int goujian(SSTable &S){ cout << "请输入你需要构建的表的大小" << endl; int tiaoshu; cin >> tiaoshu; S.R = new ElemType[tiaoshu]; for(int i=1;i<=tiaoshu;i++){ cin >>S.R[i].key>>S.R[i].name; S.length++; } cout << "构建完成" << endl; } int erfenchazhao(SSTable S,KeyType k,int i){ //i为计量进行多少次比较查找成功 int low=1,high = S.length,mid=0; cout << "请输入你要查找的信息的关键字" << endl; cin >> k; i=0; while(low<=high){ mid = (low + high)/2; if(k==S.R[mid].key) return mid; else if(k<S.R[mid].key) high = mid-1; else low=mid; i++; } return 0; } int main() { int c =-1; SSTable S1; int k; while(c=0){ cout << "输入功能序号" << endl; cout << "1 构建查找表 2 二分查找" << endl; cin >> c; int i; switch(c){ case 1: goujian(S1); break; case 2: int mid = erfenchazhao(S1,k,i); if(mid>0){ cout << "你要查找的数据元素信息:" <<endl; cout << "该信息在查找表中的序号(位置)" << mid; cout << "关键字(学号):" << S1.R[mid].key; cout << "其他信息:" << S1.R[mid].name; }else{ cout <<" 你要查找的内容不存在!"<<endl; } break; case 3: break; case 4: break; case 0: break; } } return 0; }
这是一段 C++ 代码,实现了一个二分查找算法。它定义了三个结构体类型,分别是 ElemType、SSTable 和 KeyType,其中 ElemType 表示表中的元素类型,包括关键字和名称;SSTable 表示查找表类型,包括一个指向元素数组的指针和数组长度;KeyType 表示关键字类型。主函数中,用户可以选择构建一个查找表或者进行二分查找。如果选择构建查找表,则会提示用户输入元素关键字和名称,并创建一个 SSTable 类型的对象 S1,保存元素信息。如果选择二分查找,则会提示用户输入要查找的关键字,并调用 erfenchazhao 函数进行查找。erfenchazhao 函数接受 SSTable 类型的对象 S、要查找的关键字 k 和计数器 i 作为参数,返回查找结果,如果找到则返回元素在表中的位置,如果未找到则返回 0。在寻找过程中,每次比较将计数器 i 加 1,最后返回 i 的值,表示查找过程中进行的比较次数。如果找到了元素,则输出该元素的关键字和名称,否则输出“你要查找的内容不存在”。
阅读全文