1 // ch09_02.cpp : 二分查找法
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 #include <cstdlib>
 7 using namespace std;
 8 
 9 int bin_search(int data[50],int val);
10 int _tmain(int argc, _TCHAR* argv[])
11 {
12     int data[50];
13     int val=1;
14     for (int i=0;i<50;i++)
15     {
16         data[i]=val;
17         val+=rand()%5+1;
18     }
19 
20     cout<<"数据内容："<<endl;
21     for (int i=0;i<5;i++)
22     {
23         for (int j=0;j<10;j++)
24             cout<<i*10+j+1<<"-"<<data[i*10+j]<<" ";
25         cout<<endl;
26     }
27 
28     cout<<"请输入搜索键值："<<endl;
29     while(1)
30     {
31         int num=0;
32         cin>>val;
33         if (val==-1)
34             break;
35         num=bin_search(data,val);
36         if (num==-1)
37             cout<<"没有找到"<<endl;
38         else
39             cout<<"在"<<num+1<<"处找到"<<data[num]<<endl;
40                 
41     }
42     cout<<endl;
43     system("pause");
44     return 0;
45 }
46 
47 int bin_search(int data[50],int val)
48 {
49     int low,high,mid;
50     low=0,high=49;
51     while(low<=high && val!=-1)
52     {    
53         mid=(low+high)/2;
54         if (val<data[mid])
55         {
56             cout<<val<<"介于位置"<<low+1<<"["<<data[low]<<"]"<<"及中间位置"<<mid+1<<"["<<data[mid]<<"]"<<endl;
57             high=mid-1;
58         }
59         else if(val>data[mid])
60         {
61             cout<<val<<"介于中间位置"<<mid+1<<"["<<data[mid]<<"]"<<"及最后位置"<<high+1<<"["<<data[high]<<"]"<<endl;
62             low=mid+1;
63         }
64         else 
65             return mid;
66     }
67     return -1;
68 }
69 
70 

Rand Posts: