有15个数按大到小的顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则打印出“无此数”。
时间: 2023-05-01 15:02:09 浏览: 85
题目大意:给定一个由15个数按大小顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中,则打印出“无此数”。
折半查找法是在有序数组中查找一个元素的算法,首先确定待查找区间的中间元素,如果该元素等于查找元素,则返回该元素在数组中的位置,否则该中间元素比查找元素大,则在待查找区间的左半部分继续查找,反之则在右半部分继续查找,直至找到或者待查找区间为空。
具体实现是,先将待查找区间的左右端点确定为数组的第一个和最后一个元素的下标,然后不断缩小待查找区间的范围,每次确定中间元素,将该元素与查找元素进行比较,根据比较结果更新待查找区间的左右端点,直至找到目标元素或者待查找区间为空。
如果最终没有找到目标元素,则打印出“无此数”。
相关问题
有15个数按小由到大顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数在数组中的下标。
折半查找法是一种二分查找法,适用于有序数组。在数组中选择中间的数与要查找的数进行比较,如果相等,则查找成功,返回下标;如果要查找的数小于中间数,则在数组的左半部分继续查找;如果要查找的数大于中间数,则在数组的右半部分继续查找,直到找到该数为止。
用c++写有15个数按小由到大顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数在数组中的下标。
好的,下面是使用C++实现的代码:
```c++
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was not present
return -1;
}
int main()
{
int arr[15] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int x;
cout << "Enter a number to search: ";
cin >> x;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
```
代码中,我们首先定义了一个长度为15的数组,然后输入一个要查找的数x,调用`binarySearch`函数进行折半查找,最后输出结果。`binarySearch`函数使用while循环实现了折半查找算法,如果找到了就返回下标,找不到就返回-1。