java二分法詳解幾種實現(xiàn)方法

java 二分法詳解幾種方法

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站制作、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)柯橋,十載網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575

二分查找(java實現(xiàn))

二分查找

算法思想：又叫折半查找，要求待查找的序列有序。每次取中間位置的值與待查關(guān)鍵字比較，如果中間位置的值比待查關(guān)鍵字大，則在前半部分循環(huán)這個查找的過程，如果中間位置的值比待查關(guān)鍵字小，則在后半部分循環(huán)這個查找的過程。直到查找到了為止，否則序列中沒有待查的關(guān)鍵字。

實現(xiàn)：

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;
  }

2.遞歸實現(xiàn)

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;
  }

時間復(fù)雜度為 O(logN)

查找第一個元素出現(xiàn)的位置（元素允許重復(fù)）

public static int biSearch(int []array,int a){
    int n=array.length;
    int low=0;
    int hi=n-1;
    int mid=0;
    while(low<hi){
      mid=(low+hi)/2;
      if(array[mid]<a){
        low=mid+1;
      }else{
        hi=mid;
      }
    }
    if(array[low]!=a){
      return -1;
    }else{
      return low;
    }
  }

查詢元素最后一次出現(xiàn)的位置

public static int biSearch(int []array,int a){
    int n=array.length;
    int low=0;
    int hi=n-1;
    int mid=0;
    while(low<hi){
      mid=(low+hi+1)/2;
      if(array[mid]<=a){
        low=mid;
      }else{
        hi=mid-1;
      }
    }
  
    if(array[low]!=a){
      return -1;
    }else{
      return hi;
    }
  }

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

當前標題：java二分法詳解幾種實現(xiàn)方法
分享鏈接：http://chinadenli.net/article4/jiihoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、云服務(wù)器、網(wǎng)站導(dǎo)航、、營銷型網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

java二分法詳解幾種實現(xiàn)方法