在排好序的基础上折半查找
时间: 2024-04-04 08:29:07 浏览: 38
折半查找,也叫二分查找,是一种查找算法。它的基本思想是:在有序数组中,先找到数组中间的数,然后将要查找的值与中间数进行比较,如果相等,就返回中间数的下标;如果要查找的值比中间数小,则在数组左半部分继续进行折半查找;如果要查找的值比中间数大,则在数组右半部分继续进行折半查找,直到找到要查找的值为止。
折半查找的时间复杂度为O(log n),比顺序查找的时间复杂度O(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
```