打开《Java语言程序设计与应用》_从基础向熟练进发_3.5 数组查找

【摘要】 本书摘自《Java语言程序设计与应用》一书中第3章，第5节，由徐俊武编著。

3.5 数组查找

数组查找是指从一个数组中查找某一个数据，数据存在的话，返回角标号， 没有相应的数据，返回-1。我们要知道某一个数据在某一个数组中的位置，数 据和数组都是不确定的，这是一个通用的解法。编写程序就是用通用的方法，来 解决具体的问题，主函数中是确定的问题，功能化函数中是通用的解法。因此， 输入中有两个形参。在写形参时，要标注类型和变量名。

查找有两种结果，找到和找不到。找得到时，直接返回角标值；找不到时，返 回- 1。在数组对数据编号时，都是从0开始编的，返回了- 1,就表示数组中没 有该数据，也不存在相应的角标号。

如下程序：

class ArrayDemo{

public static void main(String[] args){int[] arr={4,1,8,7,3,9,2);

Int index=getIndex(arr,8);

System.out.println("index="+index);

)

public static int getIndex(int[] arr,int key){

for(int x=0;x

if(arr[x]==key)

retrun x;

return- 1;

这里 return-1 写在for语句的外面也挺奇怪的。其实这里牵涉 return 能 够返回多个值的问题，从定义方法后，进入 for语句。 for 循环里面，如果 if 成 立，就返回一个。for里面有三种情况：有多个返回值，有一个返回值，无返回值。 无论 for里面是什么情况，接着都会返回一个一1的值。但是数组里面有对应数 据的时候，得到的返回值就是第一次出现数据的角标号，后面的返回值都不管， 这里值得深思。无论怎样，最后都会返回一个-1的值，如果前面有对应数据， 有返回角标值，那么这个一1就无所谓；如果前面没有返回值，那么这里的-1就 是唯一的返回值，也就意味着数组中没有对应的数据。

接下来介绍折半查找，折半查找可以提高查找的效率。能够执行折半查找 的数据有一个必要前提：数据必须是有序的。

折半查找和查找功能是一样的，都是为了在数组中查找某一个数据，并返回 它的角标号。只是在具体执行的时候，思路有些不一样，但是方法的输入和返回 值都是一样的。举例说明。

13 15 19 28 33 45 78 106

0 1 2 3 4 5 6 7(角标)

折半查找时，核心有两步，折半和对比。折半和对比要进行多次，这就意味 着有循环的存在。循环结构的三种语句 while,do-while,for 中，三者都是同一 种结构的语句，本质上是一样的，应用的方向不一样。

初始化表达式中，就必须有一个 mid,来和给定数据进行对比，当两者不相等 时，就进入循环；如果相等，就直接返回折半值。进入循环后，下一个折半值，以及 min 和 max 也要重新确定，这也是对比的情况得来的。对比永远只有一个式子，折 半值和给定数据是否相等。进入循环后，肯定要有退出循环的条件，不然循环将一 直进行，如果max

开始时，我们要确定中间角标的大小，中间角标=(首角标+尾角标)/2,由 于这是java 计算机语言中的计算，所以中间角标的结果绝对不会是浮点型，都 是 int类型。这一连串数据是有大小顺序的，但是并没有规定，相差都为1。算 法如下：

Mid=(0+7)/2=3;

Arr[mid]==key false;

If(key>arr[mid])

Mid=mid+1;

If (key

Mid=mid- 1;

Mid=(max+min)/2=(4+7)/2=5;

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。