注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Aspirer's blog

停止维护,新博客地址:http://aspirer.wang/

 
 
 

日志

 
 

二分查找  

2009-03-28 21:29:51|  分类: 学习心得 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

二分查找 - aspirer - Aspirers blog

#include <iostream>

using namespace std;

int erfen(int *arr, int key, int low, int high)
{
 int i = low;
 int j = high;
 int mid;
 if (key > arr[high] || key < arr[low])
 {
  cout << "non-exist !" << endl;
  return -1;
 }
 while (i <= j)
 {
  mid = (i + j)/2;
  cout << "i = " << i
   << ", j = " << j
   << ", mid = " << mid
   << endl;
  if (arr[mid] < key)
  {
   i = mid + 1;
  }
  else if (arr[mid] > key)
  {
   j = mid - 1;
  }
  else
  {
   return mid;
  }
 }
 return -1;
}


int main()
{
 int arr[] = {0, 1, 2, 3, 5, 6, 7, 8, 9, 10};
 int pos = erfen(arr, 4, 0, 9);
 if (pos >= 0)
 {
  cout << arr[pos] << endl;
 }
 return 0;
}

 



/*
*erfen_chaxun.h;
*二分法查询一组输入数列中的某个数,没有则给出提示。
*/

#ifndef ERFEN_CHAXUN_H
#define ERFEN_CHAXUN_H

#include <vector>
#include <iostream>
#include <algorithm>

class EFCX
{
private:
 double query_num ;
 std::vector < double > nums ;
public:
 EFCX() : query_num( 0 )
 {}
 
 void input_nums()
 {
  std::cin.clear() ;
  fflush( stdin ) ;
  fflush( stdout ) ;
  
  std::cout << "输入要查询的数:" ;
  std::cin >> query_num ;
  double temp ;
  std::cout << "输入一组数据,以任意字母结束:" << std::endl ;
  while ( std::cin >> temp )
  {
   nums.push_back( temp ) ;
  }

  sort( nums.begin(), nums.end() ) ;
 }

 std::vector < double >::const_iterator it_beg()
 {
  //std::cout << *nums.begin() << std::endl ;
  //返回vector类型容器的起始位置
  return nums.begin() ;
 }

 std::vector < double >::const_iterator it_end()
 {
  //std::cout << nums.end()  -nums.begin() << std::endl ;
  //返回vector类型容器的超出末端位置
  return nums.end() ;
 }

 void Query_num( std::vector < double >::const_iterator beg,
  std::vector < double >::const_iterator end ) const
 {
  
  if ( beg == end )//&& *beg != query_num
  {
   std::cout << "找不到" << query_num << "!" << std::endl ;
  }

  //end-1是为了配合第二个实参初始化在超出末端位置
  else if ( *beg != query_num
   && *(end - 1) != query_num )
  {
   if ( *(beg + (end-beg)/2 ) == query_num )
   {
    //+1是因为数组索引是从0开始的
    std::cout << "找到" << query_num << "位置为:" << beg+(end-beg)/2 - nums.begin() +1 << "。" << std::endl ;
   }
   else if ( *(beg + (end-beg)/2 ) > query_num )
   {
    //在else if ( *beg != query_num && *(end - 1) != query_num )
    //这里会end - 1,如果下面的第二个参数再-1,则重复减1一次,
    //也即少查询一个元素:(beg + (end-beg)/2 -1 )!
    Query_num( beg, (beg + (end-beg)/2 ) ) ;
   }
   else
   {
    Query_num( (beg + (end-beg)/2 + 1), end ) ;
   }
  }
  else
  {
   if ( *beg == query_num )
   {
    //+1是因为数组索引是从0开始的
    std::cout << "找到" << query_num << "位置为:" << beg - nums.begin() +1 << "。" << std::endl ;
   }
   else if ( *(end-1) == query_num )
   {
    //最后一个数据的索引是end-beg
    std::cout << "找到" << query_num << "位置为:" << end - nums.begin() << "。" << std::endl ;
   }
  }
  
 }
};


#endif



/*
*erfen_chaxun.cpp;
*/

#include "erfen_chaxun.h"

int main()
{
 EFCX array1 ;
 array1.input_nums() ;
 //array1.it_beg();
 //array1.it_end();
 array1.Query_num( array1.it_beg(), array1.it_end() ) ;

 return 0 ;
}

  评论这张
 
阅读(532)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018