算法第二章上机实践报告

标签：复杂   nbsp   size   二分查找   out   i++   复杂度   return   位置   

算法第二章上机实践报告

　　1.实践题目

改写二分搜索算法

　　2.问题描述

设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

　　3.算法描述

#include 

#include 

using namespace std;

int main(){

    int array1[100];

    int i,j,mid,x,number;

    int result = 0;

    cin >> number;//输入数字个数

    cin >> x;//输入目标数

    for(i = 0;i

        cin >> array1[i];//输入数组

    }

    int left = 0,right = number - 1;//设左右指针指向数组头尾

    if(array1[left] > x)

        cout

    if(array1[right]

        cout

    while(left

        if(x == array1[left]){ //x是第一个数

            cout

            result == 1;

            break;

        }

        if(x == array1[right]){ //x是最后一个数

            cout

            result == 1;

            break;

        }   

        int mid = (left + right) / 2;

        if(x == array1[mid]) {

            cout

            result == 1;

            break;

        }

        if(x

            right = mid-1;

        }

        if(x > array1[mid]) {

            left = mid+1;

        }

    }

    if(result == 0){

            for(i = 1;i

                if(array1[i] > x && array1[i - 1]

                    cout

            }

        }

    return 0;

}

　　4.算法时间及空间复杂度分析（要有分析过程）

该题使用二分搜索算法，先描述所查找数字x大于或小于数组中全部元素的情况。进行2次判断。然后假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n/4，…，n/2^k，其中k是循环的次数。如果最终找不到该数字，就输出最接近该数的左右两个数字， 最坏的情况是经过k次二分之后,每个区间的长度为1（只有1个元素）,才找到想要的元素。令n/2^k=1，可得k=log2n,（是以2为底，n的对数），所以时间复杂度为O(logn)。由于辅助空间是常数级别的所以空间复杂度是O(1)。

　　5.心得体会（对本次实践收获及疑惑进行总结）

该题目其实就是使用二分查找找元素，只不过不同的是多了两种情况，一个是x过大或者过小，另一个是没有找到是输出最接近的两个数的条件。刚开始编程时没有使用迭代的方法，而是利用for循环一步一步去寻找X，时间复杂度应为O(n)，后期经修改使用二分搜索时间复杂度降低到O(logn),程序得到优化。

算法第二章上机实践报告

标签：复杂   nbsp   size   二分查找   out   i++   复杂度   return   位置   

原文地址：https://www.cnblogs.com/tinyea/p/11565133.html