小編給大家分享一下Java怎么實(shí)現(xiàn)二分查找的變種，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

我們提供的服務(wù)有：成都網(wǎng)站建設(shè)、成都做網(wǎng)站、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、輝南ssl等。為上千企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的輝南網(wǎng)站制作公司

Java的優(yōu)點(diǎn)是什么

1. 簡單，只需理解基本的概念，就可以編寫適合于各種情況的應(yīng)用程序；2. 面向?qū)ο螅?. 分布性，Java是面向網(wǎng)絡(luò)的語言；4. 魯棒性，java提供自動(dòng)垃圾收集來進(jìn)行內(nèi)存管理，防止程序員在管理內(nèi)存時(shí)容易產(chǎn)生的錯(cuò)誤。；5. 安全性，用于網(wǎng)絡(luò)、分布環(huán)境下的Java必須防止病毒的入侵。6. 體系結(jié)構(gòu)中立，只要安裝了Java運(yùn)行時(shí)系統(tǒng)，就可在任意處理器上運(yùn)行。7. 可移植性，Java可以方便地移植到網(wǎng)絡(luò)上的不同機(jī)器。8.解釋執(zhí)行，Java解釋器直接對Java字節(jié)碼進(jìn)行解釋執(zhí)行。

具體內(nèi)容如下

普通二分查找：

先回顧一下普通的二分查找

注意：二分查找有這樣一個(gè)問題：當(dāng)數(shù)組中數(shù)有重復(fù)時(shí)，比如 ｛3，3，3，3｝ 這個(gè)數(shù)組，二分查找3時(shí)，返回的是arr[1]，也就是說二分查找并不會(huì)返回3第一次出現(xiàn)的位置0。

public class BinarySearch {
  public static <T extends Comparable<? super T>> int search(T arr[], T value) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
      int mid = (left & right) + ((left ^ right) >> 1);
      if (arr[mid].compareTo(value) == 0) {
        return mid;
      } else if (arr[mid].compareTo(value) > 0) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }
 
  public static void main(String[] args) {
    Integer[] arr = new Integer[]{1, 3, 3, 6, 7, 9};
 
    //-1
    System.out.println(search(arr, 0));
 
    //0
    System.out.println(search(arr, 1));
 
    //5
    System.out.println(search(arr, 9));
 
    //-1
    System.out.println(search(arr, 10));
 
    //2
    System.out.println(search(arr, 3));
  }
}　

二分變種：findFirst函數(shù)

在普通二分查找中，在[left....right]左閉右閉區(qū)間中查找，如果找到了值為value的元素就認(rèn)為找到了。而在這個(gè)findFirst函數(shù)中就不是如此，在[left....right]左閉右閉區(qū)間中查找，當(dāng)找到值等于value的元素后，不是讓right = mid - 1，而是讓right = mid，繼續(xù)在[left....right]左閉右閉區(qū)間中查找。最終left== right時(shí)就退出循環(huán)。

退出循環(huán)后可能找到了value值，也有可能是循環(huán)遍歷完整個(gè)數(shù)組后都沒找到value，而退出循環(huán)。

所以退出循環(huán)后還要在判斷一下是那種情況。

public class BinarySearch {
  public static <T extends Comparable<? super T>> int findFirst(T arr[], T value) {
    int left = 0;
    int right = arr.length - 1;
    //當(dāng)left>=right時(shí)退出，這里的“=”情況與二分不同
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr[mid].compareTo(value) < 0) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    // 上面循環(huán)遍歷完后。是找到了value值？還是沒找到value值？判斷一下。
    if (arr[left] == value) {
      return left;
    } else {
      return -1;
    }
  }
 
  public static void main(String[] args) {
    Integer[] arr = new Integer[]{1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9};
 
    //-1
    System.out.println(findFirst(arr, 0));
 
    //0
    System.out.println(findFirst(arr, 1));
 
    //12
    System.out.println(findFirst(arr, 9));
 
    //-1
    System.out.println(findFirst(arr, 10));
 
    //1
    System.out.println(findFirst(arr, 3));
  }
}

二分變種：fewer函數(shù)

介紹

給定一個(gè)數(shù)組，和一個(gè)變量value,從數(shù)組中找出值最接近value值而且比value小的那個(gè)數(shù)。比如 arr = {11，22，22，33 ，33，33，44，54}   value = 33。 22最接近value，而且比value小。

所以答案是2  ( 22在數(shù)組arr中的下角標(biāo) )  。

如果沒找到比value小的數(shù)，那么輸出 -1。

解決思路

用二分查找方法。每次用 arr[mid] 來與value進(jìn)行比對。小、等于，去左邊找；大，去右邊找?？赡苌弦痪涞摹暗扔凇钡那闆r你不太理解。普通二分查找是找出arr[mid] == value，而fewer函數(shù)是為了找出比value小的數(shù)，所以盡管arr[mid] == value，還得繼續(xù)去左邊找更小的值。

例子

代碼

public class BinarySearch {
  public static <T extends Comparable<? super T>> int fewer(T arr[], T value) {
    int left = 0;
    int right = arr.length - 1;
    //當(dāng)left > right 時(shí)退出
    while (left <= right) {
      int mid = (left & right) + ((left ^ right) >> 1);
      if (value.compareTo(arr[mid]) <= 0) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return right;
  }
 
  public static void main(String[] args) {
    Integer[] arrF = new Integer[]{21, 23, 25, 25, 31, 34, 37, 39, 52, 63};
 
    //3
    System.out.println(fewer(arrF, 30));
  }
}　

以上是“Java怎么實(shí)現(xiàn)二分查找的變種”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)站欄目：Java怎么實(shí)現(xiàn)二分查找的變種
文章地址：http://www.rwnh.cn/article32/psgspc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、網(wǎng)站營銷、外貿(mào)建站、網(wǎng)站設(shè)計(jì)、網(wǎng)頁設(shè)計(jì)公司、網(wǎng)站改版

廣告

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