Go语言 排序与搜索切片

Python09

Go语言 排序与搜索切片,第1张

Go语言标准库中提供了sort包对整型,浮点型,字符串型切片进行排序,检查一个切片是否排好序,使用二分法搜索函数在一个有序切片中搜索一个元素等功能。

关于sort包内的函数说明与使用,请查看 https://godoc.org/sort

在这里简单讲几个sort包中常用的函数

在Go语言中,对字符串的排序都是按照字节排序,也就是说在对字符串排序时是区分大小写的。

二分搜索算法

Go语言中提供了一个使用二分搜索算法的sort.Search(size,fn)方法:每次只需要比较㏒₂n个元素,其中n为切片中元素的总数。

sort.Search(size,fn)函数接受两个参数:所处理的切片的长度和一个将目标元素与有序切片的元素相比较的函数,该函数是一个闭包,如果该有序切片是升序排列,那么在判断时使用 有序切片的元素 >= 目标元素。该函数返回一个int值,表示与目标元素相同的切片元素的索引。

在切片中查找出某个与目标字符串相同的元素索引

当我们要从一个序列中查找一个元素的时候,二分查找是一种非常快速的查找算法,二分查找又叫折半查找。

它对要查找的序列有两个要求,一是该序列必须是有序的(即该序列中的所有元素都是按照大小关系排好序的,升序和降序都可以,本文假设是升序排列的),二是该序列必须是顺序存储的。

如果一个序列是无序的或者是链表,那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件,是由二分查找算法的原理决定的。

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

二分查找能应用于任何类型的数据,只要能将这些数据按照某种规则进行排序。然而,正因为它依赖于一个有序的集合,这使得它在处理那些频繁插入和删除操作的数据集时不太高效。这是因为,对于插入和操作来说,为了保证查找过程正常进行,必须保证数据集始终有序。相对于查找来说,维护一个有序数据集的代价更高。此外,元素必须存储在连续的空间中。因此,当待搜索的集合是相对静态的数据集时,此时使用二分查找是最好的选择。

二分查找算法的原理如下:

二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素。

二分查找法实质上是不断地将有序数据集进行对半分割,并检查每个分区的中间元素。

此实现过程的实施是通过变量left和right控制一个循环来查找元素(其中left和right是正在查找的数据集的两个边界值)。

二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说,最多可以进行O(㏒₂n)次分区。对于二分查找,这表示最终可能在最坏的情况下执行的检查的次数:例如,在没有找到目标时。所以二分查找的时间复杂度为O(㏒₂n)。

参考:

https://www.html.cn/qa/other/23018.html

https://www.cnblogs.com/idreamo/p/9000762.html

用汇编语言编写程序,实现二分法字符查找的功能。

要求完成的主要任务:

(1)屏幕提示输入字符串;

(2)将字符进行大小写变换(全部大写或小写)并显示;

(3)屏幕提示输入待查找字符;

还是到威客上面悬赏吧