1. class ArrayDemo6
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 int[] arr = {23,99,45,32,76,87,98,86};
   
6.                
   
7.                 System.out.println("index="+halfSearch(arr,99));
   
8.                 System.out.println("index1="+binarySearch(arr,99));
   
9.         }
   
10. 
    
11.         /*
    
12.         *方法：遍历查找
    
13.         *参数：整型数组；
    
14.         *参数：key,要查找的值
    
15.         *返回值：角标
    
16.         */
    
17.         public static int ergodicSeek(int[] arr, int key)
    
18.         {
    
19.                 for(int x=0; x<arr.length; x++)
    
20.                 {
    
21.                         if(arr[x]==key)
    
22.                                 return x;
    
23.                 }
    
24.                 return -1;
    
25.         }
    
26. 
    
27.         /*
    
28.         *方法：折半查找
    
29.         *参数：整型数组
    
30.         *参数：key，要查找的值
    
31.         *返回值：角标
    
32.         */
    
33.         public static int halfSearch(int[] arr,int key)
    
34.         {
    
35.                 int max,min,mid;
    
36.                 max = arr.length-1;
    
37.                 min = 0;
    
38.                 mid = (max + min)>>1;
    
39.                 while(arr[mid]!=key)
    
40.                 {
    
41.                         if(key>arr[mid])
    
42.                                 min = mid+1;
    
43.                         else if(key<arr[mid])
    
44.                                 max = mid-1;
    
45.                         if(max<min)
    
46.                                 return -min-1;
    
47.                         mid = (max + min)>>1;
    
48.                 }
    
49.                 return mid;
    
50.         }
    
51.         /*
    
52.         *方法：折半查找
    
53.         *参数：整型数组
    
54.         *参数：key,要查找的值
    
55.         */
    
56.         public static int binarySearch(int[] arr,int key)
    
57.         {
    
58.                 int max,min,mid;
    
59.                 max = arr.length-1;
    
60.                 min = 0;
    
61.                 while(min<=max)
    
62.                 {
    
63.                         mid = (max + min)>>1;
    
64.                         if(key>arr[mid])
    
65.                                 min = mid+1;
    
66.                         else if(key<arr[mid])
    
67.                                 max = mid-1;
    
68.                         else
    
69.                                 return mid;
    
70.                 }
    
71.                 return -min-1;
    
72.         }
    
73. }
    

复制代码

普通的遍历查找能找到key值，可是折半(二分法)查找虽然效率高，但是却找不到指定的key值，能不能再优化呢？

折半查找的前提,数组必须是有序的,先对数组排序

同学，折半查找，首先要求就是数组是有序的。

水木桶 发表于 2012-9-2 14:42
同学，折半查找，首先要求就是数组是有序的。

API 中的Arrays.binarySearch(int[] arr, int key)  方法中也没有设计排序呀，这是为什么？

明白了，这个数组在传进去之前就要是有序的！

折半查找，前提是数组是有序的。按你的程序要求数组是递增的。

二分（折半查找法）：

        角标是有序的，直接获取中间角标上的元素座位判断的依据。
        中间角标 = （头角标+尾角标）/2；（0+5）/2=2;
        数组[中间角标]=25；
        if（key>中间元素）
                头角标= 中间角标+1；
        else if(key<中间元素)
                尾角标=中间角标-1；

        在缩小范围的数组中继续取中间值。
                中间角标 = （头角标+尾角标）/2；（3+5）/2=4;
                数组[中间角标]=57；

在折半的过程总 头角标不断的增大 尾角标不断的在减小。

if（头角标>尾角表）
        return - 1;


演示：二分查找法
：前提：只能对有序的数组进行查找。
public static int binarySearch(int[] arr,int key)
{
//1，需要定义三个变量，用于记录住角标的变化。
        int min,max,mid;
        min = 0;
        max=arr.length-1;
        //只要min和max之间有距离，就有了折半的可能折半多次，使用while循环。

        while(min<max)
                //获取中间角标
                mid =(max+min)/2;//mid =(max=min)>>1;
                //获取中间角标上的元素和key进行比较，
                //来确定min和max的新值，或者叫做。不去确定新的查找范围
                if（key>arr[min]）
                min=mid+1;
                else if(key>arr[mid]
                        max=mid-1;
                else
                        return mid;
               
                )
                return -1;
}

给楼主看个小例子：希望可以帮到您 这里面的方法呵呵。
/*
        思考题：
                有一个有序的数组，要求如果往这个数组中添加一个元素，还能继续保证这个数组有序，
                那么这个元素的位置如何获取？

        思路:
        1,既然是有序的数组，还要获取位置。这就是在查找。而且有序就可以使用二分查找。
        2,如果要插入的元素在数组中已存在，只要找这个元素的位置就是要插入的位置。
        3,如果要插入的元素在数组中不存在。
        */

/*

        //二分查找法的另一种写法。
        public static int binarySearch_2(int[] arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length-1;
                mid = (max+min)>>1;

                while(arr[mid]!=key)
                {
                        if(key>arr[mid])
                                min = mid + 1;
                        else if(key<arr[mid])
                                max = mid - 1;

                        if(min>max)
                                return -1;
                        mid = (max+min)>>1;
                }

                return mid;

        }



*/
class ErFen1
{
        public static void main(String[] args)
        {
                int[] arr={2,3,5,7,44,55,67,88};
                        int zhao1=zhao(arr,67);
                                System.out.println("zhao1="+zhao1);
        }
        public static int zhao(int[] arr,int key)
        {
                //1，需要定义三个变量,用于记录住角标的变化。
                int min,max,mid;
                        min=0;
                        max=arr.length-1;
                        //只要min和max之间有距离，就有了折半的可能，而且有可能折半多次，使用while循环。。
                        while(min<=max)
                        {
                                        //获取中间角标。
                                        mid=(max+min)/2;
                                       
                        //获取中间角标上的元素和key进行比较。
                        //来确定min和max的新值。或者叫做，确定新的查找范围。
                                        if(key>arr[mid])
                                                min=mid+1;
                                        else if(key<arr[mid])
                                                max=mid-1;
                                        else
                                                return mid;
                       
                        }
                        return min;
               
       
        }


}

当数组元素无序的时候，可以采用数组遍历比较的方式查找；

       当数组元素是按一定顺序排列的时候，我们可以采用折半查找方法。

class  ChaZhao

{

       public static void main(String[] args)

       {

              //int[] arr={3,1,5,4,7,9};

              //int Index=getIndex(arr,2);

              //System.out.println("Index="+Index); //如果数组里面有两个要找的数，则为第一个。

              int[] arr={1,2,3,4,5,6,7};

              int Index=halfSearch(arr,6);

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

       }

       //数组查找

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

{

       for(int x=0;x<arr.length;x++)

              {

                     if(arr[x]==key)

                            return x;  //这个return执行过后下面的return就不再执行

              }

              return -1; //数组角标都是从0开始的，当没有找到时，角标为-1即为没有找到该值。

}

//折半查找

public static int halfSearch(int[] arr,int key)

{

              int min,max,mid;

              min=0;

              max=arr.length-1;

              mid=(max+min)/2;

              while(arr[mid]!=key)

              {

                     if (key>arr[mid])

                            min=mid+1;

                     else if(key<arr[mid])

                            max=mid-1;

                     if(min>max)

                            return -1;

                     mid=(max+min)/2;

              }

                     return mid;

}

}

折半查找，首先要求数组是有序的，否则就要实现排序，然后才能折半查找，要不就用遍历查找！