二分查找

摘要: 二分查找

</td> </tr> <tr> <td height="35" valign="top" class="ArticleTeitle"><table width="737" border="0"> <tr> <td width="731" height="108"> </td> </tr> </table>
举个例子：你要在英文字典中找一个单词，二分查找相当于在中间打开字典，然后确定这个单词是在书的头一半中，还是在后一半中。然后您从中间打开下一半，并确定这个单词是在这一半的头一半中，还是在后一半中，这样，你重复这一折半查找过程，直到找到自己正在寻找的单词。比起顺序查找，它的效果十分明显。
当然，二分查找只适合已排序的数据。下面这个程序搜索一个整数数组，查找并打印过程，并在结束时，显示找到指定值时所需要的步数：

public class arrayBinary{

      public static int bsearch(int array[],int value){

        boolean found=false;

        int high=array.length-1;

        int low=0;

        int cnt=0;//查找步数

        int mid=(high+low)/2;

        System.out.println("Looking for "+value);

        while(!found&&(high>=low)){

           System.out.print(" Low "+low+" Mid "+mid);

           System.out.print(" High "+high);

           if(value==array[mid])

               found=true;

           else

               if(value< array[mid])

                  high=mid-1;

               else

                  low=mid+1;

           mid=(high+low)/2;

           cnt++;

         }

         System.out.println();

         System.out.println("Steps "+cnt);

         return((found)?mid:-1);

       }

     public static void main(String[] args){

        int array[]=new int[100];

        for(int i=0;i< array.length;i++)

               array[i]=i;

        System.out.println("Resulte "+bsearch(array,67));

        System.out.println("Resulte "+bsearch(array,33));

        System.out.println("Resulte "+bsearch(array,1));

        System.out.println("Resulte "+bsearch(array,1001));       

     }

  }

程序结果：

C:\java>javac arrayBinary.java

C:\java>java arrayBinary
Looking for 67
Low 0 Mid 49 High 99 Low 50 Mid 74 High 99 Low 50 Mid 61 High 73 Low 62 Mid 67 High 73
Steps 4
Resulte 67

Looking for 33
Low 0 Mid 49 High 99 Low 0 Mid 24 High 48 Low 25 Mid 36 High 48 Low 25 Mid 30 High 35 Low 31 Mid 33 High 35
Steps 5
Resulte 33

Looking for 1
Low 0 Mid 49 High 99 Low 0 Mid 24 High 48 Low 0 Mid 11 High 23 Low 0 Mid 5 High
10 Low 0 Mid 2 High 4 Low 0 Mid 0 High 1 Low 1 Mid 1 High 1
Steps 7
Resulte 1

Looking for 1001
Low 0 Mid 49 High 99 Low 50 Mid 74 High 99 Low 75 Mid 87 High 99 Low 88 Mid 93
High 99 Low 94 Mid 96 High 99 Low 97 Mid 98 High 99 Low 99 Mid 99 High 99
Steps 7
Resulte -1

C:\java>

function TempSave(ElementID) { CommentsPersistDiv.setAttribute("CommentContent",document.getElementById(ElementID).value); CommentsPersistDiv.save("CommentXMLStore"); } function Restore(ElementID) { CommentsPersistDiv.load("CommentXMLStore"); document.getElementById(ElementID).value=CommentsPersistDiv.getAttribute("CommentContent"); } </td> </tr> <tr>

↑返回目录
前一篇: i=i++的迷惑
后一篇: replaceAll函数