# include <stdlib.h>
# include <string.h>
# include <stdio.h>

void main()
{
	/* 聲明子函數 */
	int binary(char *ptr[], char *str, int n);    /* 查找函數聲明 */
	void insert(char *ptr[], char *str, int n, int i);    /* 插入函數聲明 */

	char *temp, *ptr1[6];
	int i;
	printf("請為字符形指針數組賦初值：\n");
	for (i=0; i<5; i++)
	{
		ptr1[i] = (char *)malloc(20);    /* 為指針分配地址后 */
		gets(ptr1[i]);    /* 輸入字符串 */
	}
	ptr1[5] = (char *)malloc(20);
	printf("\n");

	printf("original string:\n");
	for(i=0; i<5; i++)    /* 輸出指針數組各字符串 */
		printf("%s\n", ptr1[i]);

	printf("\ninput search string:\n");
	temp = (char *)malloc(20);
	gets(temp);    /* 輸入被插字符串 */

	i=binary(ptr1, temp, 5);    /* 尋找插入位置i */
	printf("i = %d\n", i);

    insert(ptr1, temp, 5, i);    /* 在插入位置i處插入字符串 */
	printf("output strings:\n");

	for(i=0; i<6; i++)    /* 輸出指針數組的全部字符串 */
		printf("%s\n", ptr1[i]);
}

int binary(char *ptr[], char *str, int n)
{ 
	/* 折半查找插入位置 */
	int hig, low, mid;
	low = 0;
	hig = n-1;
	if(strcmp(str,ptr[0]) < 0) 
		return 0;
    /* 若插入字符串比字符串數組的第0個小，則插入位置為0 */
	if(strcmp(str,ptr[hig]) > 0) 
		return n;
    /* 若插入字符串比字符串數組的最后一個大，則應插入字符串數組的尾部 */
    while(low <= hig)
	{
		mid = (low + hig)/2 ;
		if (strcmp(str,ptr[mid]) < 0)
			hig = mid - 1;
		else if(strcmp(str,ptr[mid]) > 0)
			low = mid + 1;
		else 
			return mid;    /* 插入字符串與字符串數組的某個字符串相同 */
	}
	return low;    /* 插入的位置在字符串數組中間 */
}

void insert(char *ptr[], char *str, int n, int i)
{
	int j;
	for(j=n; j>i; j--)    /* 將插入位置之后的字符串后移 */
		strcpy(ptr[j], ptr[j-1]);
	strcpy(ptr[i], str);    /* 將被插字符串按字典順序插入字符串數組 */
}