//此程序实现数组的折半查找法
//问:这个程序的问题是，第一个方法halfSearch_1没问题。调用hS_2方法时如果传入的key大于数组中的最大
//值时候会抛出ArrayIndexOutOfBoundsException的错误。小于最小值也不会。请问是怎么回事啊。
//   下面的异常处理合适吗？
public class HalfSearch
{
        public static void main(String[] args)
        {
                int[] arr = {1,3,5,6,8,9,44,55,67,90};
                int index = halfSearch_2(arr,98);
                sop(index);
        }
        //第二种方法，以min小于等于max为条件
        public static int halfSearch_2(int[] arr,int key)
        {
                int min = 0,max = arr.length,mid;

                while(min<=max)
                {
                        //if(key>arr[max]||key<arr[min])
                                //return -1;
                        mid = (min +max)>>1;
                        if(key<arr[mid])
                                max = mid -1;
                        else if(key>arr[mid])
                                min = mid +1;
                        else
                                return mid;
                       
                }
                return -1;
        }
        /*
        //这是对第二种方法。异常处理后的方法。
        public static int halfSearch_3(int[] arr,int key)
        {
                int min = 0,max = arr.length,mid;
                try
                {
                        while(min<=max)
                        {
                               
                                        //if(key>arr[max]||key<arr[min])
                                                //return -1;
                                        mid = (min +max)>>1;
                                        if(key<arr[mid])
                                                max = mid -1;
                                        else if(key>arr[mid])
                                                min = mid +1;
                                        else
                                                return mid;
                        }
                }
                catch(ArrayIndexOutOfBoundsException e)
                {
                                System.out.print("超过数组最大值！");
                }
                return -1;
        }
        */
        //第一种方法，以key不等于中间值为判断条件。
        public static int halfSearch_1(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid = (min + max)/2;
                while(arr[mid]!=key)
                {
                        if(key<arr[min]||key>arr[max])
                                return -1;
                        if(key>arr[mid])
                        {
                                min = mid +1;
                        }
                        else if(key<arr[mid])
                        {
                                max = mid -1;
                        }
                        if(min>max)
                                return -1;
                        mid = (min + max)/2;
                       
                }
                return mid;
        }
        public static void sop(Object obj)
        {
                System.out.print(obj);
        }
}

public class HalfSearch
{
      public static void main(String[] args)
      {
              int[] arr = {1,3,5,6,8,9,44,55,67,90};
              int index = halfSearch_2(arr,90);
              if(index == -1)
                      System.out.println("Not Found");
              else
                      sop(index+1);
      }
      //第二种方法，以min小于等于max为条件
      public static int halfSearch_2(int[] arr,int key)
      {
              int min = 0,max = arr.length,mid;
              while(max>0&&min<arr.length&&min<=max)
              {
                      //if(key>arr[max]||key<arr[min])
                              //return -1;
                      mid = (min+max)>>1;
                      if(key<arr[mid])
                              max = mid -1;
                      else if(key>arr[mid])
                              min = mid +1;
                      else
                              return mid;
                     
              }
              return -1;
      }
//修改此处就不会报错