在排好序的基础上折半查找

折半查找，也叫二分查找，是一种查找算法。它的基本思想是：在有序数组中，先找到数组中间的数，然后将要查找的值与中间数进行比较，如果相等，就返回中间数的下标；如果要查找的值比中间数小，则在数组左半部分继续进行折半查找；如果要查找的值比中间数大，则在数组右半部分继续进行折半查找，直到找到要查找的值为止。

折半查找的时间复杂度为O(log n)，比顺序查找的时间复杂度O(n)要快很多。但是，折半查找的前提是数组必须是有序的，如果数组没有经过排序，则需要先进行排序，这会增加算法的时间复杂度。

总的来说，折半查找是一种效率比较高的查找算法，在处理大量数据时非常有用。

相关问题

C语言代码实现随机输入（或随机产生）30个数，采用顺序、折半查找在排好序的数据中完成查找任务

以下是使用顺序和折半查找在排好序的数据中查找一个数字的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模块来生成随机数，以及顺序查找和折半查找算法来查找数据：

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