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

更新時間：2017年12月13日 15:10:21 作者：GoldArowana

這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)二分查找的變種，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了Java實現(xiàn)二分查找的變種，供大家參考，具體內(nèi)容如下

普通二分查找：

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

注意：二分查找有這樣一個問題：當(dāng)數(shù)組中數(shù)有重復(fù)時，比如｛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的元素就認(rèn)為找到了。而在這個findFirst函數(shù)中就不是如此，在[left....right]左閉右閉區(qū)間中查找，當(dāng)找到值等于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;
    //當(dāng)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中的下角標(biāo) ) 。

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

解決思路

用二分查找方法。每次用 arr[mid] 來與value進行比對。小、等于，去左邊找；大，去右邊找?？赡苌弦痪涞摹暗扔凇钡那闆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 時退出
    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));
  }
}

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

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: