我们知道折半查找只能在有序的数组里才能使用。

其实在插入排序过程中，大家细心的话会发现，每次找插入位置时，这段元素是有序的，那么在这里为使用折半查找提供了条件。

 但是用传统的折半查找肯定不行，因为我们这里要找的是要插入的位置

例如：42，53， 64， 85， 58这5个元素在插入排序里就是58前面的元素全部有序，我们要找的是58应该插入的位置，应该是在64所在的位置

而这个64所在的位置就是我们折半查找要查找的位置，其实就是53<58<64，在这里我对折半查找稍作改进

int binsearch(int *A,int first,int last,int x){	int mid=0;	int a=0;	while(first>=0&&last>=0&&(last-first)>1)	{		mid=(first+last)/2;		a=COMPARE(A[mid],x);		switch(a)		{		case 1:		last=mid;    break;                  //在这里对折半查找稍作改动last=mid-1;改为last=mid;		case 0:		return mid;    break;		case -1:	first=mid;   break;                  //这里也对折半查找稍作改动		}	}	mid=(first+last)/2;	if((COMPARE(A[mid],x)==1)&&mid==0)                   //当插入位置w为A[0]时，要另外讨论		return 0;	else                                                 		return last;}

首先last=mid-1;改为last=mid;     first=mid+1;也改为了first=mid;循环退出条件改为while(first>=0&&last>=0&&(last-first)>1)

如此一来，我们最终总会得到上面示例中first位于53所在的位置，last位于64所在的位置，一般情况下我们只要返回last就够了

但有一种情况要注意，就是当要查找的位置位于元素最前面，例如：42,56,78,98,31

如果按照上述方法，first位于42所在的位置，last位于56所在的位置，如果此时返回last肯定是不对的。

所以对于这种情况，要另外讨论mid=(first+last)/2;  if((COMPARE(A[mid],x)==1)&&mid==0)    return 0;

再一次取mid,如果mid==0;说明first位于42所在的位置，last位于56所在的位置，而且if(COMPARE(A[mid],x)==1),如果A[mid]>x,即42>31,那么这时该插入的位置应该位于A[0]

以下是折半插入排序部分代码：

void Insertionsort2(int *A,int n){	int i=0;	int j=0;	int v=0;		for(i=1;i
    
     v)		{			j=binsearch(A,0,i-1,v);   //用折半查找找到要插入的位置			for(;i>j;i--)			{				A[i]=A[i-1];			}			A[j]=v;		}	}}
    

下面是我的测试代码，已测试过

//折半插入排序Insertsort2()#include 
    
     #include 
     
      #include 
      
       #define COMPARE(x,y)  (((x)>(y))?1:(((x)==(y))?0:-1))void print(int *A,int n);void Insertionsort2(int *A,int n);int binsearch(int *A,int first,int last,int x);void main(){	int n=0;	int i=0;            //循环变量	int *A=NULL;	printf("你想要多少个随机数?  ");	scanf("%d",&n);	if(n<1)		n=1;	A=(int*)malloc(n*sizeof(int));	if(A==NULL)	{		printf("Out of memory!\n");		exit(1);	}	srand(time(NULL));                         //产生0~999之间的n个随机数	for(i=0;i
       
        v)		{			j=binsearch(A,0,i-1,v);   //用折半查找找到要插入的位置			for(;i>j;i--)			{				A[i]=A[i-1];			}			A[j]=v;		}	}}		void print(int *A,int n){	int i=0;	for(i=0;i
        
         =0&&last>=0&&(last-first)>1)	{		mid=(first+last)/2;		a=COMPARE(A[mid],x);		switch(a)		{		case 1:		last=mid;    break;                  //在这里对折半查找稍作改动last=mid-1;改为last=mid;		case 0:		return mid;    break;		case -1:	first=mid;   break;                  //这里也对折半查找稍作改动		}	}	mid=(first+last)/2;	if((COMPARE(A[mid],x)==1)&&mid==0)                   //当插入位置w为A[0]时，要另外讨论		return 0;	else                                                 		return last;}
        
       
      
     
    

对于算法方面的问题，确实不容易想，为这个问题我也苦恼了很长时间，发了帖子也没有有价值的回复，甚至有人嘲讽你，但我最终还是做出来了

这个算法可能不是很好，但是这真是我自己想出来的，完全原创。

大家有什么别的思路完全可以交流交流，呵呵O(∩_∩)O~