Board logo

標題: binarySearch() [打印本頁]

作者: tonyh    時間: 2021-12-27 19:59     標題: binarySearch()

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

[attach]12586[/attach]
  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. */
複製代碼

作者: 李沛昂    時間: 2021-12-27 20:23

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

  4. public class Ch00 {

  5.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  6.         String raw[];
  7.         int len, n[], x;
  8.         Ch00() 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 Ch00();
  42.         }
  43. }
複製代碼

作者: 黃宇綸    時間: 2021-12-27 20:25

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. main()
  4. {
  5.     int n;
  6.     while(cin>>n) {
  7.         vector<int> v;
  8.         int x;
  9.         for(int i=0;i<n;i++) {
  10.             cin>>x;
  11.             v.push_back(x);
  12.         }
  13.         cin>>x;
  14.         cout<<lower_bound(v.begin(),v.end(),x)-v.begin()<<"\n";
  15.     }
  16.     return 0;
  17. }
複製代碼

作者: 黃宇瑄    時間: 2021-12-27 20:30

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.Arrays;
  4. public class Ch00 {
  5.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  6.         String raw[];
  7.         int len, n[], x;
  8.         Ch00() 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.                                 index=index*-1-1;
  34.                         System.out.println(index);
  35.                         System.out.println();
  36.                 }
  37.         }
  38.         public static void main(String[] args) throws Exception {
  39.                 new Ch00();
  40.         }
  41. }
複製代碼

作者: 戴嘉禾    時間: 2022-7-1 15:56

  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. }
複製代碼





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