首页 > 代码库 > 折半查找算法

折半查找算法

/* Date:2014.12.16

    折半查找算法,也叫二分查找,用于对拥有唯一元素的查找。

    需要先经过按序排序后才能进行。只对有序表适用。
*/
//先快速排序:(此处增序,也可降序)
void QuickSort(int *arr,int left,int right)
{
int key,temp,ltemp,rtemp;

ltemp = left;
rtemp = right;
key=arr[(left + right) / 2];

while (ltemp <= rtemp)
{
while (arr[ltemp] < key)
{
ltemp ++;
}
while (key < arr[rtemp])
{
rtemp --;
}
if (ltemp <= rtemp)
{
temp = arr[ltemp];
arr[ltemp] = arr[rtemp];
arr[rtemp] = temp;
ltemp ++;
rtemp --;
}
}

if (left < rtemp)
{
QuickSort(arr,left,rtemp);
}
if (ltemp < right)
{
QuickSort(arr,ltemp,right);

}
//对有序表(有序递增)进行折半查找 

int BinarySearch(int *arr,int n,int x)
{
int low,mid,high;
low = 0;
high = n - 1;
while (low <= high)
{
mid =(low + high) / 2;
if (arr[mid] == x)
{
return mid;

else if (arr[mid] > x)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}



折半查找算法