zhuhouyu
zhuhouyu
2016-12-08 14:16
采纳率: 100%
浏览 963
已采纳

C语言的相关问题,求助大神们。

图片说明原题如图所示。C语言中,设计函数:search(),用折半查找法在已排序的n个数种查找指定的数据,若存在,返回其所处的位置,否则,将其插入适当位置使数据仍有序。
这个程序我已经写完了前半段,但是后半段的那个插入其中使其保持原来的顺序,我的是从大到小排列,不知道后半段代码该如何写了。求助大神们。
int search (int *d,int n,int key){
int low,high,mid,i;
low=0;
high=n-1;
while( low <= high){
mid=(low+high)/2;
if(key==d[mid]) return mid;
else if(key>d[mid]) high=mid-1;
else low = mid + 1;
}
return 0;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • qq_34479762
    qq_34479762 2016-12-08 16:17
    已采纳

    注意数组要足够大,不然插入新元素时下标会越界
    int Search(int *d, int n, int key) {
    int low, high, mid;
    low = 0;
    high = n-1;
    while( low <= high){
    mid = (low + high) / 2;
    if(key == d[mid])
    return mid;
    else if(key > d[mid])
    high = mid - 1;
    else low = mid + 1;
    if((low == mid || high == mid) && d[mid] != key) {
    if(d[mid] > key) {
    for(int i = n ; i > mid + 1; i--)
    d[i] = d[i - 1];
    d[mid + 1] = key;
    return 666;
    } else {
    for(int i = n; i > mid; i--)
    d[i] = d[i - 1];
    d[mid] = key;
    return 666;
    }
    }
    }
    return 0;
    }

    点赞 评论
  • u012934325
    墨笙弘一 2016-12-08 15:38

    给你思路,你已经对无序数组实现了排序,然后才可以使用二分查找,如果该数存在,返回他所在的位置,如果不存在,你用二分法查找了位置,把那个数字插入到比他大的数字后面,其余的数字再存储到数组中
    你要插入的位置就是你用二分法结束循环的那个(low+high)/2的位置处,你可以新建一个数组把要插入的数之前的先存入然后在存入该数再存入后面的数字,因为你二分查找知道了在插值的位置

    点赞 评论

相关推荐