/*************************************************************************
> File Name: bin_search.c
> Author:heathcliff
> Mail:---------------------
> Created Time: 04月05日 星期二 18时12分46秒
************************************************************************/
#include
#define M 5
/*折半查找法*/
int bin_search(int A[],int n,int key)
{
int low,high,mid;
low = 0;
high = n-1;
while(low <= high){
mid = (low + high)/2;
if(A[mid] == key)
return mid;
else if(A[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
/*查找失败*/
return -1;
}
/*直接插入排序*/
int insert_sort(int A[],int n)
{
int i,j,temp; //temp 保存中间值
for(i = 1;i < n; i++){
temp = A[i];
j = i - 1;
while(j >= 0 && temp < A[j]){ //找到插入位置
A[j+1] = A[j];
j -- ;//j向后移动
}
A[j+1] = temp; //插入temp处的值
}
}
int main(void)
{
int A[M];
int i;
int n , m;
printf("请输入数组的值：");
for(i = 0;i < M;i++)
scanf("%d",&A[i]);
printf("\n你输入的值为：");
for(i = 0;i < M;i++)
printf("[%d]",A[i]);
printf("\n");
insert_sort(A,M);
for(i = 0;i < M;i++)
printf("[%d]",A[i]);
printf("\n");
printf("请输入你要查找的值:\n");
scanf("%d",&n);
m = bin_search(A , M , n);
if(-1 != m){
printf("排序后,你查找的值在数组的第%d 的位置\n",m);
}
else
printf("查找失败\n");
return 0;
}
分析：
输入的值为：10,5,9,8,7
1. 排序
首先 i = 1;temp = A[i] = 5;
j = i -1 = 0;
判断j>= 0 && temp < A[0] = 10 ?，判断成立
A[1] = A[0] = 10;//值交换
j = -1;
判断 j> = 0 判断不成立
A[1] = 5;
如此一来：输入的值变为了5,10,9,8,7
第二轮：i = 2; temp = A[2] = 9;
j = i - 1 = 1;
判断 j>=0 && temp
A[2] = A[1] = 10;//交换值
j = 0;
判断 j>= 0&& temp < A[0] ?判断不成立
A[1] = temp = 9;
这么一搞：输入值就又变成了：5,9,10,8,7
以此类推，即可将输入数组有序排列为 5,7,8,910
2. 折半查找
假设要找的值为7 ， 即key = 7
low = 0；
high = 4；
mid = 2；
A[2] = 8 > key ；
high = mid - 1 = 1;
mid = 0;
A[0] = 5 < 7;
low = mid + 1 = 1;
mid = 1;
A[mid] = key;
找到7的位置
