二分法

二分查找(java实现)

二分查找

搜索数据与有序数组中间元素比较以确定在中间元素左边还是右边，如果在右边，则调整最小搜索索引值，然后进入下次循环；如果在左边，则调整最大搜索索引值，然后进入下次循环；如果相等则当前位置就是查找数据所在位置，停止循环

算法思想：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

public static int sort(int []array,int a,int lo,int hi){

    if(lo<=hi){

      int mid=(lo+hi)/2;

      if(a==array[mid]){

        return mid+1;

      }

      else if(a>array[mid]){

        return sort(array,a,mid+1,hi);

      }else{

        return sort(array,a,lo,mid-1);

      }

    }

    return -1;

  }

非递归代码

public static int biSearch(int []array,int a){

    int lo=0;

    int hi=array.length-1;

    int mid;

    while(lo<=hi){

      mid=(lo+hi)/2;

      if(array[mid]==a){

        return mid+1;

      }else if(array[mid]<a){

        lo=mid+1;

      }else{

        hi=mid-1;

      }

    }

    return -1;

  }