首页 > 代码库 > 折半查找算法
折半查找算法
/* 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;
}
折半查找算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。