00:00
同学们,我们来看一下查找算法。那么查找呢,不是数据结构,而是一种算法好不好,那这点大家要必须明确,我们来看看在Java中我们常用的查找算法有哪些呢?第一种就是顺序查找,也叫线性查找。就是按照这个顺序来比对,然后找到我们需要的数据,第二个呢叫二分查找,也叫折半查找,这个呢是一个比较经典的查找方法。呃,很多这个学计算机的呢,都会去要求必须掌握二分查找对不对,查找效率呢也很也很高,我们再看还有第三种就叫叫做差值查找。叉值查法,呃,插值查找呢,我们后面会详细介绍,还有一种叫飞波纳器查找,也叫黄金分割点查找,那么这是我们后面要讲的四种,我们先给同学们来看一下线性查找算法。线性查找算法呢,特别简单,它是这样子的,各位同学那怎样做呢?就说我给你一个数列,这个数列可以是有序的,也可以是无序的,注意啊,顺线性查找,它这个序列可以是有序也可以是无序。
01:13
那么我们要求如果找到了,就返回它的下标提示找到并返回下标,这个很简单,我们来走一圈给大家,给大家写一写啊,来打开我们的这个。Eclipse我们写个包包,这个包呢,我们起个名字叫做search ch。线性查找,OK,那现在呢,我们写一个方法啊,写个类叫做sequence。Seq sequence顺序的意思,Search。SEARCH。勾上主方法,我们来写一写。把它拿掉啊,首先呢,我们拿一个数组过来。N我说了这个数组呢,可以有序也可以无序,比如说我们找一个没有顺序的对吧,负一,然后呢,34,然后89 OK,这是一个序列,无序序列。
02:12
就是没有。没有顺序的这个数组,那现在怎么查找呢?我们写一个方法对吧,我们写一个方法,那public。Public public static,那么我们返回一个什么呢?返回一个in的,In的我们叫sequence。Search,那你把什么传给我呢?各位,很简单,你把数组给我,然后再把你要查找的值给我就可以了。那刚才讲过顺序就是我们叫做呃,线性查找呢,线性。线性查找它是。逐一比对,逐一比对。比对啊,发现发现有相,发现有相同的值时,就返回下标。
03:09
是这样子的吧,那代码呢,非常简单,其实就是个变例就可以了,For循环I ti等于零对不对?I小于什么呢?我们这个数组的NI加加。非常简单对不对,我们格式化一般,嗯,那那怎么做呢?如果我们发现R这个I,它等于等于我们要查找的这个值没问题,这时我们就提示一句话。其实我们就菩提直接返回就可以了啊I。哎,返回这个下标就返回下标,否则我们返回一个负一就完事,当然就写完了,看到没有很简单,那但是大家有发现,我目前呢是找到一个就返回,如果说我们假如要找所有的值,比如说我假设我这个数字里面有两个11,而另外一个11在最后,那你没办法,你只能把这个全部遍历,然后把这个查找照的这个下边呢,放放到一个集合里面去也行。
04:08
现在呢,我们做了一个比较简单的,就是找到一个就返回,我做一个说明啊。这里,这里我们实现的线性查找。对线性查找。查找是。查找是找到一个,找到一个满足条件的,满足条件的值就返回。就返回了,没问题吧,就返回了,呃,那么如果同学们想找到多个呢,你可以遍历全部,然后把下标放在一个集合里面,返回的就不是一个int了,而是一个集合。好吧,这个同学们自己去做一下就行了,因为比较简单,我就呃,不啰嗦了,来,我们拿到这个值in。Index等于什么呢?等于这个。Sequence。Search把数组放进去,现在我们要找的值,比如说是11。
05:03
对不对,比如说一,那我判断一下,如果index等于什么呢?等于负一,就说明我们没有找到。所以吧,我们说出一句话就行了。说出一句什么话呢?哎,我们就输出这句话,就是没有查找到,没有查找到哪个字呢?没有查找到你要找的这个字对不对,11没有查找到,呃,那如果找到怎么办呢?如果找到我们把它下标打出来。写句话一样的。怎么写呢?我们说找到了,找到下标。为多少呢?OK,把这个index打出来就可以,同样啊,我们运行一把,大家可以看到,现在呢,我们找到下边为多少呢?二正确的。对不对,那如果说我我找一个负的11,现在找不到,找不到怎么办呢?返回一个负一啊,我们我们又打出来了,好同学们,关于一个线性查找呢,我们就讲到这儿,非常简单啊,过一下就行了。
06:04
好,那现在呢,我们准备讲二分查找。
我来说两句