Aaron学习笔记

少壮不努力,长大没饭吃!
posts - 4, comments - 13, trackbacks - 0, articles - 37

折半查找

Posted on 2009-03-24 15:47 赞劲小子 阅读(4061) 评论(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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理