算法第二章上机实践报告
标签：分治法 二分法 stream info 技术 cout 存在 col lse
1.实践题目
PTA算法 7-1 二分查找
2.问题描述
3.算法描述
1 #include 2 using namespace std;
3
4 int number = 0; //定义比较次数
5
6 //left和right分别代表a[]最小值下标和最大值下标
7 void binarySearch(int a[], int x, int left, int right){
8 //如果x不存在，输出-1
9 if(left > right){
10 cout "-1" endl;
11 cout number;
12 }
13 else{
14 number++; //每次查找都是一次比较
15 int mid = (left + right) / 2;
16 //当二分查找的中间值就是要找的x，则输出下标和比较次数
17 if(a[mid] == x){
18 cout endl;
19 cout number;
20 }
21 //如果中间值大于x，则递归查找中间值左边的一半数组
22 else if(a[mid] > x){
23 binarySearch(a, x, left, mid - 1);
24 }
25 //如果中间值小于x，则递归查找中间值右边的一半数组
26 else if(a[mid] x){
27 binarySearch(a, x, mid + 1, right);
28 }
29 }
30 }
31
32 int main(){
33 int n, x;
34 int a[1000];
35 cin >> n;
36 for(int i = 0; i ){
37 cin >> a[i];
38 }
39 cin >> x;
40 binarySearch(a, x, 0, n - 1);
41 return 0;
42 }
4.算法时间及空间复杂度分析
（1）时间复杂度：
每经过一次比较，数组a的大小就变为原来的一半，则有T(n) = O(1) + T(n/2) = O(logn)
（2）空间复杂度：
因为定义的变量a[]所分配的空间大小不随n和x的变化而变化，所以该算法的空间复杂度S(n) = O(1)
5.心得体会
该题主要是要理解分治法的思想，二分法顾名思义就是讲一个大的问题分为两个较小的子问题进行求解，我这里用的是递归的算法，在将a[mid]和x进行比较后，要分清当x
遇到的主要问题是开始没有想到number++放在哪里比较合适，没有想到每进行一次二分查找就是一次比较的情况。
算法第二章上机实践报告
标签：分治法 二分法 stream info 技术 cout 存在 col lse
原文地址：https://www.cnblogs.com/jewfer-03-08/p/11567543.html
评论