Board logo

標題: binarySearch() [打印本頁]
作者: tonyh    時間: 2022-4-18 18:43     標題: 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;

  5. public class Ch01 {

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

  43.         public static void main(String[] args) throws Exception {
  44.                 new Ch01();
  45.         }
  46. }

  48. /*
  49. 0 1 2 3 4 5 6 7 8 9 10

  51. 1 3 6 6 6 6 6 6 6 7 8
  52. 6

  54. 1 3 6 6 6 6 6 6 6 7 8
  55. 5

  57. 1 3 6 6 6 6 6 6 6 7 8
  58. 1
  59. */
複製代碼
作者: 駱顗安    時間: 2022-4-18 19:04

本帖最後由 駱顗安 於 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);


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




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2