查找问题。 在数组中进行查找是数组经常用到的一种操作。根据数组的不同特点，查找的方法也很多，这些方法各有利弊。本例介绍两种最常用的查找方法，更多的查找方法有兴趣的读者可以查阅数据结构方面的资料。 (1

查找问题。 在数组中进行查找是数组经常用到的一种操作。根据数组的不同特点，查找的方法也很多，这些方法各有利弊。本例介绍两种最常用的查找方法，更多的查找方法有兴趣的读者可以查阅数据结构方面的资料。 (1) 顺序查找 从第一个元素开始逐一比较，直到末尾。 算法：一列数放在无序的数组a[1]----a[n]中，待查找的数放在x 中，把x与a数组中的元素从头到尾一一进行比较查找。用变量pos表示a数组元素下标，pos初值为0，使x与a[pos]比较，如果x不等于a[pos]，则使p=p+1，不断重复这个过程；一旦x等于a[pos]则退出循环；另外，如果pos大于数组长度，循环也应该停止。 以下代码中的布尔变量 found初始值为 False ，如果找到就被赋值 True。函数返回值是布尔值。

1. a=[1, 2, 3, 4, 5, 6, 8, 20, 24, 31, 35]    
2. x=24   
3. def sequentialSearch(a,n):    
4.      pos = 0 
5.      found = False 
6.      while pos < len(a) and not found: 
7.           if a[pos] == n: 
8.                found = True 
9.           else: 
10.                pos=pos+1 
11.      return found 
12.  
13. print(sequentialSearch(a, x)) 

上述代码的输出结果如下： True 如果将第2行中x的值改为25，则输出结果如下： Falseuy0100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
分析上面的程序，如果数据项不在列表里，唯一的判定办法就是把全部项逐个比较一番。如果表中有 n 个数据，顺序查找就需要 n 次比较。但是分析没有这么简单，有三种情形可能发生：最好的情况下，第一个项就是我们要找的，只有 1 次比较。最差的情况下，需要 n 次比较，全部比较过之后才知道找不到。在平均情况下，会发现是列表的一半，即平均要比较 n/2 次。 假如表中数据项以某种方式排序了，怎样来快速查找呢？下面来介绍折半查找，也就是二分法查找。uy0100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
(2) 折半查找 算法：设n个有序数（从小到大）存放在数组a[1]----a[n]中，要查找的数为x。用变量low、high、middle 分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，middle=( low+high)//2，折半查找的算法如下： ① x=a[middle]，则已找到退出循环，否则进行下面的判断； ② x<a[middle]，x必定落在low和middle -1的范围之内，即high= middle -1； ③ x>a[middle]，x必定落在middle +1和high的范围之内，即low= middle +1； ④ 在确定了新的查找范围后，重复进行以上比较，直到找到或者low<=high。 将上面的算法写成如下函数，若找到则返回该数所在的下标值，没找到则返回-1。uy0100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
(2) 折半查找

1. a=[1, 2, 3, 4, 5, 6, 8, 20, 24, 31, 35]    
2. x=24   
3. def binary_Search(a,n):    
4.     low = 0   
5.     high = len(a)-1   
6.     while low <= high:    
7.         middle = (low+high)//2    
8.         if a[middle] == n:    
9.             print('find it') 
10.             return middle+1    
11.         elif a[middle] < n:   
12.             low = middle + 1    
13.         else:   
14.             high = middle - 1    
15.     print('find failed') 
16.     return -1     
17. print(binary_Search(a,x)) 

上述代码的输出结果如下： find failed -1 如果将第2行改为x=24，则代码的输出结果如下： find it 9