返回列表 發帖

binarySearch()

本帖最後由 tonyh 於 2022-4-18 18:47 編輯

我們可利用 Arrays 類別或 Collections 類別底下的 binarySearch() 方法,作二分搜尋以快速地找到目標對象的位置或插入點。留意使用二分搜尋法的先決條件是,資料必須是已排序,同時若有重複資料則回傳值可能會不如預期,這時候必須再以迴圈找出精確的位置。

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.Arrays;

  4. public class Ch01 {

  5.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  6.         String raw[];
  7.         int len, n[], x;
  8.         Ch01() throws Exception
  9.         {
  10.                 while(true){
  11.                         raw=br.readLine().split(" ");
  12.                         len=raw.length;
  13.                         n=new int[len];
  14.                         for(int i=0; i<len; i++)
  15.                                 n[i]=Integer.parseInt(raw[i]);
  16.                         x=Integer.parseInt(br.readLine());
  17.                         int index=Arrays.binarySearch(n, x);
  18.                         if(index>=0)
  19.                         {
  20.                                 if(index>0)
  21.                                 {
  22.                                         while(true)
  23.                                         {
  24.                                                 index--;
  25.                                                 if(n[index]!=x)
  26.                                                 {
  27.                                                         index++;
  28.                                                         break;
  29.                                                 }
  30.                                         }
  31.                                 }
  32.                         }else
  33.                         {
  34.                                 index=index*-1-1;
  35.                         }
  36.                         System.out.println(index);
  37.                         System.out.println();
  38.                 }
  39.         }

  40.         public static void main(String[] args) throws Exception {
  41.                 new Ch01();
  42.         }
  43. }

  44. /*
  45. 0 1 2 3 4 5 6 7 8 9 10

  46. 1 3 6 6 6 6 6 6 6 7 8
  47. 6

  48. 1 3 6 6 6 6 6 6 6 7 8
  49. 5

  50. 1 3 6 6 6 6 6 6 6 7 8
  51. 1
  52. */
複製代碼

本帖最後由 駱顗安 於 2022-4-18 19:10 編輯
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.Comparator;
  6. import java.util.TreeSet;
  7. public class P1 {
  8.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  9.         int t,n,c,s,l,k[];
  10.         String raw[];
  11.         boolean b;
  12.         ArrayList<Integer> al=new ArrayList<Integer>();
  13.         P1() throws Exception{
  14.                 raw=br.readLine().split(" ");
  15.                 n=raw.length;
  16.                 k=new int[n];
  17.                 for(int i=0;i<n;i++) k[i]=ip(i);
  18.                 t=Integer.parseInt(br.readLine());
  19.                 int index=Arrays.binarySearch(k, t);
  20.                 if(index<0) index=-index-1;
  21.                 else {
  22.                         while(index>0&&k[index-1]==t) index--;
  23.                 }
  24.                 System.out.println(index);


  25.         }
  26.         int ip(int y) {
  27.                 return Integer.parseInt(raw[y]);
  28.         }
  29.         public static void main(String[] args) throws Exception {
  30.                 new P1();
  31.         }
  32. }
複製代碼

TOP

返回列表