binarySearch()

tonyh

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

1. import java.io.BufferedReader;
   
2. import java.io.InputStreamReader;
   
3. import java.util.Arrays;
   
4. 
   
5. public class Ch01 {
   
6. 
   
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.         }
    
42. 
    
43.         public static void main(String[] args) throws Exception {
    
44.                 new Ch01();
    
45.         }
    
46. }
    
47. 
    
48. /*
    
49. 0 1 2 3 4 5 6 7 8 9 10
    
50. 
    
51. 1 3 6 6 6 6 6 6 6 7 8
    
52. 6
    
53. 
    
54. 1 3 6 6 6 6 6 6 6 7 8
    
55. 5
    
56. 
    
57. 1 3 6 6 6 6 6 6 6 7 8
    
58. 1
    
59. */

複製代碼

李沛昂

1. import java.io.BufferedReader;
   
2. import java.io.InputStreamReader;
   
3. import java.util.Arrays;
   
4. 
   
5. public class Ch00 {
   
6. 
   
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.         }
    
42. 
    
43.         public static void main(String[] args) throws Exception {
    
44.                 new Ch00();
    
45.         }
    
46. }

複製代碼

黃宇綸

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. }

複製代碼

黃宇瑄

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. }

複製代碼

戴嘉禾

1. import java.io.BufferedReader;
   
2. import java.io.InputStreamReader;
   
3. import java.util.Arrays;
   
4. 
   
5. public class Ch01 {
   
6. 
   
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.         }
    
42. 
    
43.         public static void main(String[] args) throws Exception {
    
44.                 new Ch01();
    
45.         }
    
46. }

複製代碼