#include<iostream.h>
#include<iomanip.h>
template <class T>
class Array
{
T *set
int n
public:
Array(T *data,int i){set=datan=i}
~Array(){}
void sort()// 排序
int seek(T key)// 查找指定的元素
T sum()// 求和
void disp()// 显示所有的元素
}
template<class T>
void Array<T>::sort()
{
int i,j
T temp
for(i=1i<ni++)
for(j=n-1j>=ij--)
if(set[j-1]>set[j])
{
temp=set[j-1]set[j-1]=set[j]set[j]=temp
}
}
template <class T>
int Array<T>::seek(T key)
{
int i
for(i=0i<ni++)
if(set==key)
return i
return -1
}
template<class T>
T Array<T>::sum()
{
T s=0int i
for(i=0i<ni++)
s+=set
return s
}
template<class T>
void Array<T>::disp()
{
int i
for(i=0i<ni++)
cout<<set<<
cout<<endl
}
void main()
{
int a[]={6,3,8,1,9,4,7,5,2}
double b[]={2.3,6.1,1.5,8.4,6.7,3.8}
Array<int>arr1(a,9)
Array<double>arr2(b,6)
cout<<arr1:<<endl
cout<<原序列:arr1.disp()
cout<<8在arr1中的位置:<<arr1.seek(8)<<endl
arr1.sort()
cout<<排序后:arr1.disp()
cout<<arr2:<<endl
cout<<原序列:arr2.disp()
cout<<8.4在arr2中的位置:<<arr2.seek(8.4)<<endl
arr2.sort()
cout<<排序后:arr2.disp()
}
1 引言
有序序列元素查找是python算法中典型且重要的技能,通过对有序序列元素查找的学习,我们可以更快的解决关于有序序列查找的相关问题,也可以更好的体现出我们的解题思维逻辑能力和提高代码水平。
查找元素。一般地,我们可以用for循环进行遍历,再用if语句进行查找。相对于for循环,二分法更加方便。二分法思想 对于已按照关键字排序的序列,经过一次比较后,可将序列分割成两部分,然后只在有可能包含待查找元素的一部分中继续查找,并根据试探结果继续分割,逐步缩小查找范围,直至找到或找不到为止。
2 问题描述
示例:如何查找有序序列中某一的元素
输入:[1,2,3,4,5,6,……,100] 61 #查找的元素
输出:61
3 算法描述
在这里我们主要使用二分法查找。二分法主要是与给定的一列序数中的中位数进行比较,然后再选取范围进行查找。如在[1,2,3,4,……,100]中查找61。先取1—100之间的中位数50进行比较,因为50比61小,所以排除1—50之间的数,再用51—100之间的中位数75进行比较,因为75大于61‘所以排除75—100的元素。然后反复地用这个方法排除多余的元素,直到剩下需要查找的元素(61)。
4 结语
有序序列中元素的查找有两种方法:一是用for循环进行遍历查找。二是二分法进行查找。对于会执行很多次的查找时采用二分法比较方便。
附件
def my_func(my_list, searched_number): #二分法
start_number_index = 0
end_number_index = len(my_list) - 1
while start_number_index <= end_number_index:
mid_number_index = (start_number_index = end_number_index) // 2
mid_number = my_list[mid_number_index]
if mid_number <searched_number:
start_number_index = mid_number_indexn+ 1
elif mid_number >searched_number:
end_number_index = mid_number_index - 1
else:
return '找到了需要查找的数字%d'% searched_number
my_list = list(range(1,101))
searched_number = 61
print(my_func(my_list, mid_number))# 结果 找到了需要查找的数字 61
序列 (sequence)是Python最基本的一种数据结构。
序列中的每个元素都有编号,即其位置或索引,其中第一个元素的索引为0,第二个元素的索引为1,依此类推。Python的序列索引支持负数,-1表示序列的最后一个元素,这是Python不同其他很多种语言不同的地方。
Python内置了多种序列,列表、元组、字符串是其中最常用的三种,本文为你描述各种序列的通用操作。
索引从0开始,索引号为0的元素为1,greeting的索引号为0的元素为'H'。
你可能注意到'Hello'和'H'都用单引号包围,这是Python不同于其他语言的另一个地方。Python并没有专门用于表示字符的数据类型,因此一个字符就是一个只包含一个元素的字符串。
Python的序列索引支持负数,-1表示倒数第一个元素。
切片 (slicing)操作用于访问序列特定 范围 内的元素。在一对方括号内使用两个索引,并用冒号隔开:
注意到,返回的序列并未包含愿序列的第6个元素7,就相当于数学集合中的 左闭右开区间 操作。
换言之,你提供两个索引来指定切片的边界,其中第一个索引指定的元素包含在切片内,但第二个索引指定的元素不包含在切片内。
保留冒号,省略第一个索引,表示从序列起始位置开始切片;省略第二个索引,表示切片到序列末尾,包含最后一个元素:
这个操作的效果是:在指定的区间内间隔取元素,语法格式为:
例如:
步长为正数时,它从起点移到终点,而步长为负数时,它从终点移到起点。
可以使用加法运算(+运算符)拼接两个序列:
从错误消息可知,不能拼接列表和字符串,虽然它们都是序列。一般而言,不能拼接不同类型的序列。
将序列与数x 相乘时,将重复这个序列x 次来创建一个新序列:
初始化一个长度为10的空列表:
成员资格检查判定一个元素是否存在于集合中,如存在返回True,否则返回False,实际上是一个布尔表达式。
语法:
例如:
内置函数 len 返回序列包含的元素个数,而 min 和 max 分别返回序列中最小和最大的元素。
Python通用的序列操作有:索引、切片、乘法、成员资格检查、长度、最小值和最大值。