Java怎么實現(xiàn)二分查找的變種

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

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

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

具體內(nèi)容如下

普通二分查找：

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

注意：二分查找有這樣一個問題：當數(shù)組中數(shù)有重復時，比如 ｛3，3，3，3｝ 這個數(shù)組，二分查找3時，返回的是arr[1]，也就是說二分查找并不會返回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的元素就認為找到了。而在這個findFirst函數(shù)中就不是如此，在[left....right]左閉右閉區(qū)間中查找，當找到值等于value的元素后，不是讓right = mid - 1，而是讓right = mid，繼續(xù)在[left....right]左閉右閉區(qū)間中查找。最終left== right時就退出循環(huán)。

退出循環(huán)后可能找到了value值，也有可能是循環(huán)遍歷完整個數(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;
    //當left>=right時退出，這里的“=”情況與二分不同
    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ù)

介紹

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

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

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

解決思路

用二分查找方法。每次用 arr[mid] 來與value進行比對。小、等于，去左邊找；大，去右邊找。可能上一句的“等于”的情況你不太理解。普通二分查找是找出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;
    //當left > right 時退出
    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怎么實現(xiàn)二分查找的變種”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！