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

java 二分法詳解幾種方法

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

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

二分查找

算法思想：又叫折半查找，要求待查找的序列有序。每次取中間位置的值與待查關鍵字比較，如果中間位置的值比待查關鍵字大，則在前半部分循環(huán)這個查找的過程，如果中間位置的值比待查關鍵字小，則在后半部分循環(huá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;
  }

時間復雜度為 O(logN)

查找第一個元素出現(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)/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://sd-ha.com/article4/jiihoe.html

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

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

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

久久久精品一区ed2k-女人被男人叉到高潮的视频-中文字幕乱码一区久久麻豆樱花-俄罗斯熟妇真实视频

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