C语言二分法编程问题

Question

已有一个已排好序的数组（如{5，12，22，34，45，55，67，78，89，98}），要求输入一个数后，按原来排序的规律将它插入到该数组中，并用二分法查找新插入的数所在位置（下标）。假设：所有的数都互不相同。
求写思路和代码

Answer 1

/* 二分法插入排序的算法源程序*/

#include<stdio.h>

#define MAXNUM 100
typedef int KeyType;
typedef int DataType;

typedef struct {
KeyType key; /* 排序码字段 */
/*DataType info; 记录的其它字段 */
} RecordNode;

typedef struct {
int n; /* n为文件中的记录个数，n<MAXNUM */
RecordNode record[MAXNUM];
} SortObject;

void binSort(SortObject * pvector) { /* 按递增序进行二分法插入排序 */
int i, j, left, mid, right;
RecordNode temp;
RecordNode *data = pvector->record;

for( i = 1; i < pvector->n; i++ ) {
temp = data[i];
left = 0; right = i-1; /* 置已排序区间的下、上界初值 */
while (left <= right) {
mid = (left + right)/2; /* mid指向已排序区间的中间位置 */
if (temp.key < data[mid].key)
right = mid-1; /* 插入元素应在左子区间 */
else left = mid+1; /* 插入元素应在右子区间 */
}
for (j = i-1; j >= left; j--)
data[j+1] = data[j]; /* 将排序码大于ki的记录后移 */
if (left != i) data[left] = temp;
}
}

SortObject vector={10, 49,38,65,97,76,13,27,49,50,101};

int main(){
int i;
binSort(&vector);
for(i = 0; i < vector.n; i++)
printf("%d ", vector.record[i]);
getchar();
return 0;
}

追问

补两个问题，我给你提高悬赏100分。
1如何采用二分查找算法确定插入点？写出关键代码
2如果原数据中已经存在与新插入的数相等的数，用二分法查找到的下标一定是新插入数的位置吗？为什么？此时应如何理解所输出的下标值？

追答

二分法插入排序

算法思想简单描述：
在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们
中间的那个元素比，如果小，则对前半再进行折半，否则对后半
进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间
的所有元素后移，再把第i个元素放在目标位置上。

1、二分法查找插入位置
如果R[i]<R[m]成立，那右指针就要向左移动中间指针一位，否则，左指针要向左移动中间指针一位。反复查找，直到左指针大于右指针时停止。
2、插入
由1中得到的左指针其实就是元素要插入的位置。

Answer 2

/*=========================================================================
工程名称： 练习
组成文件： main.c
功能描述： 在一个排好序的数据中用二分查找法，找出需要的数据
程序分析： 首先得从小到大排好序，二分再比较，不等则继续二分，直到高低碰头遍历结束
维护记录： 2014-09-11 v1.1
=========================================================================*/
#include <stdio.h>

//二分法对以排好序的数据进行查找
int binary_search(int array[],int value,int size)
{
int low=0,high=size-1,mid;

while(low<=high) //只要高低不碰头就继续二分查找
{
mid=(low+high)/2;
if(value==array[mid]) //比较是不是与中间元素相等
return mid;
else if(value > array[mid]) //每查找一次，就判断一次所要查找变量所在范围，并继续二分
low=mid; //如果大小中间值，下限移到中间的后一个位，上限不变，往高方向二分
else
high=mid; //上限移到中间的前一个位，往低方向二分
}
return -1;
}
int main(void)
{
int value;
int a[10]={0,1,2,3,4,5,6,7,8,9};
int n;

while(1)
{
printf("\n请输入你要查找的数字:\n");
scanf("%d",&value);
n = binary_search(a,value,10);
if(n==-1)
printf("数字没找到!\n");
else
printf("查找数据的下标是：%d\n",n);
}
}

追问

是编具体的问题.....