一道C语言的题目二分查找算法和插入元素

发布网友发布时间：2022-04-18 19:58

共2个回答

懂视网时间：2022-04-19 00:19

1 实例

这个模块只有几个函数，

一旦决定使用二分搜索时，立马要想到使用这个模块　

import bisect 
 
L = [1,3,3,6,8,12,15] 
x = 3 
 
x_insert_point = bisect.bisect_left(L,x)　　#在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置..这是3存在于列表中，返回左侧位置１ 
print x_insert_point 
 
x_insert_point = bisect.bisect_right(L,x) #在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置..这是3存在于列表中，返回右侧位置３ 
 
print x_insert_point 
 
x_insort_left = bisect.insort_left(L,x) #将x插入到列表L中，x存在时插入在左侧 
print L 
 
x_insort_rigth = bisect.insort_right(L,x) #将x插入到列表L中，x存在时插入在右侧　　　　 
 
print L

结果：

1
3
[1, 3, 3, 3, 6, 8, 12, 15]
[1, 3, 3, 3, 3, 6, 8, 12, 15]

实际使用中

2 bisect模块
Bisect模块提供的函数有：
(1)查找
bisect.bisect_left(a,x, lo=0, hi=len(a)) :
查找在有序列表a中插入x的index。lo和hi用于指定列表的区间，默认是使用整个列表。
bisect.bisect_right(a,x, lo=0, hi=len(a))
bisect.bisect(a, x,lo=0, hi=len(a))
这2个和bisect_left类似，但如果x已经存在，在其右边插入。
（2）插入
bisect.insort_left(a,x, lo=0, hi=len(a))
在有序列表a中插入x。如果x已经存在，在其左边插入。返回值为index。 和a.insert(bisect.bisect_left(a,x, lo, hi), x) 的效果相同。
bisect.insort_right(a,x, lo=0, hi=len(a))
bisect.insort(a, x,lo=0, hi=len(a))
和insort_left类似，但如果x已经存在，在其右边插入。
 
可以函数可以分2类，bisect*，用于查找index。Insort*用于实际插入。默认重复时从右边插入。实际常用的估计是insort。

热心网友时间：2022-04-18 21:27

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 定义数组初始长度
#define LEN 10
// 生成随机数组
void get_array(int * a, int n)
{
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        a[i] = rand() % 90 + 10;
}

// 打印数组
void print_array(int * a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// 冒泡排序
void bubble_sort(int * a, int n)
{
    int i, j, temp;
    for (j = 0; j < n - 1; j++)
    {
        for (i = 0; i < n - 1 - j; i++)
        {
            if(a[i] < a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }
}

// 二分查找，a是数组,n是数组长度,element是要查找的元素
// 找到返回元素所在的下标,否则返回-1
int binary_search(int * a, int n, int element)
{
    int low = 0, high = n - 1, middle = 0;
    middle = (low + high) / 2;
    int pos = -1;
    while (low <= high)
    {
        if (element == a[middle])
            return pos = middle;
        else if (element > a[middle])
        {
            high = middle - 1;
            middle = (low + high) / 2;
        }
        else
        {
            low = middle + 1;
            middle = (low + high) / 2;
        }
    }
    return pos;
}

// 向长度为n的数组a中插入元素element
void insert(int * a , int n, int element)
{
    a = (int *)realloc(a, n + 1);

    for (int i = 0; i <= n; i++)
    {
        if (a[i] > element)
            continue;
        for (int j = n; j > i; j--)
        {
            a[j] = a[j-1];
        }
        a[i] = element;
        break;
    }
}

// 测试
int main()
{
    int *array = (int *)malloc(LEN);
    if (NULL == array)
    {
        printf("内存分配失败\n");
        return -1;
    }
    int element = 0;
    get_array(array, LEN);
    printf("生成的随机数组:\n");
    print_array(array, LEN);
    bubble_sort(array, LEN);
    printf("排序后的数组:\n");
    print_array(array, LEN);

    printf("请输入查找的元素: ");
    scanf("%d", &element);
    int pos = binary_search(array, LEN, element);
    if (-1 == pos)
    {
        printf("未找到元素[%d]\n", element);
        insert(array, LEN, element);
        printf("插入新元素[%d]后的数组:\n", element);
        print_array(array, LEN + 1);
    }
    else
        printf("元素[%d]所在的位置为[%d]\n", element, pos);

    free(array);
    return 0;
}

追问不能运行啊

追答我的环境是RHEL6.5 32位系统,gcc4.9,编译选项-std=c99,假设文件名为main.c,编译目标文件为app,编译指令如下：
gcc -o app -std=c99 main.c
如果你是在windows的VC6下运行的话，需要把函数中所有的变量定义放在函数的开始部分，因为VC6仅支持C89标准，所以编译会报错

一道C语言的题目 二分查找算法和插入元素

一道C语言的题目二分查找算法和插入元素