在排好序的基础上折半查找
时间: 2024-04-04 15:32:29 浏览: 11
折半查找也称为二分查找,是一种高效的查找算法。它的基本思想是:将所要查找的区间一分为二,然后判断所要查找的元素在哪一半中,再把问题缩小到该半区间,直到找到该元素或者确定该元素不存在为止。
在排好序的数组中进行折半查找,可以通过以下步骤实现:
1. 确定查找区间的左右边界left和right,初始时left为0,right为数组长度减1。
2. 计算中间位置mid,即mid = (left + right) / 2。
3. 判断所要查找的元素与中间位置的元素的大小关系,如果相等则直接返回mid,如果所要查找的元素比中间位置的元素小,则在左半区间查找,将right更新为mid-1,否则在右半区间查找,将left更新为mid+1。
4. 重复2-3步,直到找到该元素或者确定该元素不存在为止。
折半查找的时间复杂度为O(log n),是一种高效的查找算法。
相关问题
C语言代码实现随机输入(或随机产生)30个数,采用顺序、折半查找在排好序的数据中完成查找任务
以下是使用顺序和折半查找在排好序的数据中查找一个数字的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 30
void generateRandomArray(int arr[], int size);
void printArray(int arr[], int size);
void bubbleSort(int arr[], int size);
int linearSearch(int arr[], int size, int target);
int binarySearch(int arr[], int size, int target);
int main()
{
int arr[SIZE];
int target, index;
// 生成随机数组
generateRandomArray(arr, SIZE);
// 排序
bubbleSort(arr, SIZE);
// 输出数组
printf("排序后的数组:\n");
printArray(arr, SIZE);
// 输入要查找的数字
printf("输入要查找的数字:");
scanf("%d", &target);
// 顺序查找
index = linearSearch(arr, SIZE, target);
if (index == -1)
printf("在数组中未找到指定数字\n");
else
printf("在数组中找到了指定数字,下标为 %d\n", index);
// 折半查找
index = binarySearch(arr, SIZE, target);
if (index == -1)
printf("在数组中未找到指定数字\n");
else
printf("在数组中找到了指定数字,下标为 %d\n", index);
return 0;
}
// 生成随机数组
void generateRandomArray(int arr[], int size)
{
srand(time(NULL));
for (int i = 0; i < size; i++)
arr[i] = rand() % 100;
}
// 输出数组
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// 冒泡排序
void bubbleSort(int arr[], int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 顺序查找
int linearSearch(int arr[], int size, int target)
{
for (int i = 0; i < size; i++)
{
if (arr[i] == target)
return i;
}
return -1;
}
// 折半查找
int binarySearch(int arr[], int size, int target)
{
int left = 0;
int right = size - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
```
该程序首先生成了一个大小为30的随机数组。然后对这个数组进行冒泡排序,以确保它是有序的。
接下来,程序提示用户输入要查找的数字。使用顺序查找和折半查找算法分别在排好序的数组中查找该数字。如果找到了该数字,程序将输出其下标;否则,程序将输出未找到该数字的消息。
随机输入(或随机产生)30个数,采用顺序、折半查找在(1)中排好序的数据中完成查找任务
好的,以下是一个示例代码,其中使用了Python的random模块来生成随机数,以及顺序查找和折半查找算法来查找数据:
```python
import random
# 生成30个随机数
data = [random.randint(1, 100) for i in range(30)]
# 排序
data.sort()
# 输出排序后的数据
print("排序后的数据:", data)
# 顺序查找
def sequential_search(data, target):
for i in range(len(data)):
if data[i] == target:
return i
return -1
# 折半查找
def binary_search(data, target):
low = 0
high = len(data) - 1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
return mid
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# 随机选择一个数作为要查找的目标值
target = random.choice(data)
# 在排序后的数据中进行顺序查找
index = sequential_search(data, target)
if index == -1:
print("{} 不在数据中".format(target))
else:
print("{} 在数据中,索引为 {}".format(target, index))
# 在排序后的数据中进行折半查找
index = binary_search(data, target)
if index == -1:
print("{} 不在数据中".format(target))
else:
print("{} 在数据中,索引为 {}".format(target, index))
```
运行结果可能如下:
```
排序后的数据: [1, 9, 11, 14, 17, 20, 21, 21, 22, 28, 33, 34, 34, 45, 49, 50, 55, 56, 59, 60, 63, 65, 68, 69, 73, 74, 76, 79, 80, 94]
60 在数据中,索引为 19
60 在数据中,索引为 19
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)