|
|
Posted on 2009-03-24 15:47 赞劲小子 阅读(4083) 评论(0) 编辑 收藏 引用 所属分类: 算法设计与分析
折半查找时，先得将数组排序。
  /**//**
 * 将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置
* 为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。
* 通过一次比较，将查找区间缩小一半。折半查找是一种高效的查找方法。它可以明显减少比较次数，
* 提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
 **/
 #include "iostream.h"
void bubble(int array[], int size);
int binarysearch(int array[], int searchkey, int low, int high, int size);
int main() {
  int array[10] = {7,6,8,5,10,9,2,4,3,1};
int array1[9] = {7,6,8,5,10,9,2,4,3};
bubble(array,10); // 数组元素为偶数
bubble(array1,9); // 数组元素为奇数
cout << binarysearch(array,1,0,9,10);
cout << binarysearch(array,4,0,8,9);
return 0;
}
void bubble(int array[], int size){
bool tag;
for(int pass = 0; pass < size - 1; pass++ ){
tag = true;
for(int j = 0 ; j < size - 1; j++)
{
int temp;
if(array[j] > array[j + 1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
tag = false;
 }
}
if(tag == true)
return ;
}
}
int binarysearch(int array[], int searchkey, int low, int high, int size){
int middle;
while(low <= high){
middle = (low + high) / 2;
if(searchkey == array[middle])
return middle;
else if(searchkey > array[middle])
low = middle + 1;
else
high = middle - 1;
}
return -1;
}
|