（三）

在有序的有N个元素的数组中查找用户输进去的数据x。

二分法查找
算法如下：
1.确定查找范围front=0，end=N-1，计算中项mid=（front+end）/2。
2.若a[mid]=x或front>=end,则结束查找；否则，向下继续。
3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。
算法复杂度分析编辑
时间复杂度
1.最坏情况查找最后一个元素（或者第一个元素）Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情况查找中间元素O(1)查找的元素即为中间元素（奇数长度数列的正中间，偶数长度数列的中间靠左的元素）
空间复杂度
S(n)=n
public class Algorithm {
      public static void main(String[] args){
            int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
            int value = binary2(a,4);
            System.out.println(value);
        }
      static int time = 0;
      public static int binary(int[] array, int value) {
          int postion = -1;
          if(array == null) {
              return postion;
          }
          int start = 0;
          int end = array.length-1;
          int middle = (end -start)/2;
          
          while(start<=end) {
              time++;
              if(value == array[middle]) {
                  postion = middle;
                  System.out.println("第"+time+"此查找，找到 postion "+ postion);
                  break;
              }else if(value <array[middle]) {
                  end = middle-1;
                  middle = (end -start)/2;
                  System.out.println("第"+time+"此查找，在左边 middle "+ middle);
              }else {
                  start = middle+1;
                  middle = start +(end -start)/2;
                  System.out.println("第"+time+"此查找，在右边 middle "+ middle);
              }
          }
          return postion;
      }
      
      public static int binary2(int[] array, int value) {
          int postion = -1;
          if(array == null) {
              return postion;
          }
          int start = 0;
          int end = array.length-1;
          while(start<=end) {
              time++;
              int middle = (end +start)/2;
              if(value == array[middle]) {
                  postion = middle;
                  System.out.println("第"+time+"此查找，找到 postion "+ postion);
                  break;
              }else if(value <array[middle]) {
                  end = middle-1;
                  System.out.println("第"+time+"此查找，在左边 middle "+ middle);
              }else {
                  start = middle+1;
                  System.out.println("第"+time+"此查找，在右边 middle "+ middle);
              }
          }
          return postion;
      }
}