返回列表 發帖

Rank: 8Rank: 8
1# 跳轉到 » 正序看帖
打印
tT
tonyh發表於 2021-12-27 19:59 | 只看該作者

binarySearch()

我們可利用 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. */
複製代碼
附件: 您需要登錄才可以下載或查看附件。沒有帳號？註冊
收藏 分享

Rank: 1
5#
戴嘉禾發表於 2022-7-1 15:56 | 只看該作者
  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. }
複製代碼
我是嘉禾豬   我是嘉禾豬   我是嘉禾豬

TOP

Rank: 1
4#
黃宇瑄發表於 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. }
複製代碼
Ivy

TOP

Rank: 1
3#
黃宇綸發表於 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. }
複製代碼
Allen

TOP

Rank: 1
2#
李沛昂發表於 2021-12-27 20:23 | 只看該作者
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.Arrays;

  5. public class Ch00 {

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

TOP

返回列表