2、二分查找的基本思想
　二分查找的基本思想是：（设R[low..high]是当前的查找区间）
（1）首先确定该区间的中点位置：

（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：
　 ①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。
　②类似地，若R[mid].key　因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。

3、二分查找算法
int BinSearch(SeqList R，KeyType K)
{ //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=1，high=n，mid； //置当前查找区间上、下界的初值
while(low<=high){ //当前查找区间R[low..high]非空
mid=(low+high)/2；
if(R[mid].key==K) return mid； //查找成功返回
if(R[mid].kdy>K)
high=mid-1; //继续在R[low..mid-1]中查找
else
low=mid+1； //继续在R[mid+1..high]中查找
}
return 0； //当low>high时表示查找区间为空，查找失败
} //BinSeareh
二分查找算法亦很容易给出其递归程序【参见练习】
4、 二分查找算法的执行过程 　　设算法的输入实例中有序的关键字序列为
(05，13，19，21，37，56，64，75，80，88，92)

#include
#include
#include

void Create_New_Array(int array[], int length)
{
srand(time(NULL));
for (int i = 0; i < length; i++)
{
array[i] = rand() % 256;
}
}

void Display_Array(int array[], int length)
{
printf("the array is:n");
for (int i = 0; i < length; i++)
{
printf("%d ", array[i]);
}
printf("n");
}

/*----------------------------------------------------------------
输入参数:数组array,起始位置start,结束位置end,待查找数x,i和j用于存放坐标
输出:如果找到返回true,否则返回false
当x小于第一个数或者大于最后一个数的时候特殊处理,详见代码
----------------------------------------------------------------*/
bool find_x(int array[], int start, int end, int x, int* i, int* j)
{
int pos;

if (x > array[end])
{
*i = end;
*j = 1000;
return false;
}
else if (x < array[start])
{
*i = -1000;
*j = start;
return false;
}

pos = (end + start) / 2;
if (array[pos] == x)
{
*i = pos;
*j = pos;
return true;
}
else if (array[pos] > x)
{
*i = pos - 1;
*j = pos;
if (end - start <= 2)
return false;
else
return find_x(array, start, pos, x, i, j);
}
else
{
*i = pos;
*j = pos + 1;
if (end - start <= 2)
return false;
else
return find_x(array, pos, end, x, i, j);
}
}

void Insert_Sort(int array[], int length)
{
int i, j, key;

for (i = 1; i < length; i++)
{
key = array[i];
for (j = i - 1; j >= 0 && array[j] > key; j--)
{
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}

int main()
{
int array[10];
Create_New_Array(array, 10);
Insert_Sort(array, 10);
Display_Array(array, 10);
int i, j, x;

printf("input the num you wanna find: ");
scanf("%d", &x);
printf("n");
bool bFind = find_x(array, 0, 9, x, &i, &j);
if (bFind)
printf("find the numn");
else
printf("cannot find the numn");
printf("i = %d, j = %dn", i, j);

return 0;
}