perl 二分法查找

《perl 二分法查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#!/usr/bin/perl-w@array=("a","f","b","c","d","ab","e",7,8,23,9);@list=sort(@array);print"pleaseinputthecontentyouwanttolookfor";print"ifthecontentexists,youwillgettheposition";chomp($k=);$min=0;$max=$#list;if($klt$list[$min]or$kgt$list[$max]){print"NOTEX

2、IST!";}else{while($kge$list[$min]and$kle$list[$max]){if($keq$list[$min]){print"thecontentisinNO.";print$min+1;print"";last;}elsif($keq$list[$max]){print"thecontentisinNO.";print$max+1;print"";last;}else{$i=($min+$max)/2;$i=int($i);if($keq$list[$i]){print"thec

3、ontentisinNO.";print$i+1;print"";last;}elsif($klt$list[$i]){$max=$i;}else{if($min==$i){print"NOTEXIST!";last;}else{$min=$i;}}}}}pleaseinputthecontentyouwanttolookforifthecontentexists,youwillgetthepositionGANOTEXIST!请按任意键继续...pleaseinputthecontentyouwanttolookf

4、orifthecontentexists,youwillgetthepositionftheinputisinNO.11请按任意键继续...pleaseinputthecontentyouwanttolookforifthecontentexists,youwillgetthepositionbthecontentisinNO.8请按任意键继续...pleaseinputthecontentyouwanttolookforifthecontentexists,youwillgetthepositionathecontenti

5、sinNO.6请按任意键继续.pleaseinputthecontentyouwanttolookforifthecontentexists,youwillgetthepositionabthecontentisinNO.7请按任意键继续.....以上为二分法的程序代码及运行结果。上述运行结果列出来四种情形：列表中不存在；位于列表边界；位于列表中任一位置;首字符一样时的查找(a,ab).算法思想;1,给出一个列表，用sort函数排序。2，输入一个content，先与排序后的列表边界处两个内容相比较，如果小于第一个或大于最后一

6、个，则判定不存在。3，若通过上述比较，则利用二分法查找。先与中间位置内容比较，若小于，则将中数赋予$max,反之，赋予$min.然后循环进行。直至中间位置所代表的内容与输入的内容一致，或完成查找依然没有相对应内容，给出“NOTEXIST”.#!/usr/bin/perl-w#my@array=1..10000;#@liste=("ab","b","di","jk",7,9);#@array=sort(@liste);print"Inputsearchitem:";chomp($input=);print"Int

7、put:--$input--";foreach(@array){if($_==$input){$m=1;my($st_index,$end_index)=(0,$#array);while($m==1){my$mid_index=int(($st_index+$end_index)/2);print"MidIndex:$mid_index";if($array[$mid_index]==$input){print"Getit:Index=$mid_index";last;}else{if($array[$mid_

8、index]>$input){$end_index=$mid_index-1;}else{$st_index=$mid_index+1;}}}}else{$m=0;}}if($m==0){print"ûÓÐÕâ¸öÊý¾Ý£¡£¡£¡";}