## 二分查找法

```int BinSearch(SeqList * R， int n , KeyType K )
{
//在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1
int low=0，high=n-1，mid；
//置当前查找区间上、下界的初值
if(R[low].key==K)
{
return 0 ;
}
while(low<=high)
{
//当前查找区间R[low..high]非空
mid=low+((high-low)/2)；
//使用 (low + high) / 2 会有整数溢出的问题
if(R[mid].key==K)
{
return mid； //查找成功返回
}
if(R[mid].key>K)
high=mid-1;
//继续在R[low..mid-1]中查找
else
low=mid+1；
//继续在R[mid+1..high]中查找
}
return -1；
//当low>high时表示查找区间为空，查找失败
}
//BinSeareh```

```int BinSearch2(int array[], int n, int v)
{
int left, right, middle;

left = -1, right = n;

while (left + 1 != right)
{
middle = left + (right － left) / 2;

if (array[middle] < v)
{
left = middle;
}
else
{
right = middle;
}
}

if (right >= n || array[right] != v)
{
right = -1;
}

return right;
}
```

1.<<编程珠玑>>
2.wiki上关于二分查找的说明:http://en.wikipedia.org/wiki/Binary_search

```int BinSearch1(int r[ ], int n, int k)
//数组r[1] ~ r[n]存放查找集合
{
low=1; high=n;
while (low<=high)
{
mid=(low+high)/2;
if (k<r[mid])  high=mid-1;
else if (k>r[mid])  low=mid+1;
else return mid;
}
return 0;
}```