標題:
binarySearch()
[打印本頁]
作者:
tonyh
時間:
2022-4-18 18:43
標題:
binarySearch()
本帖最後由 tonyh 於 2022-4-18 18:47 編輯
我們可利用 Arrays 類別或 Collections 類別底下的 binarySearch() 方法,作二分搜尋以快速地找到目標對象的位置或插入點。留意使用二分搜尋法的先決條件是,資料必須是已排序,同時若有重複資料則回傳值可能會不如預期,這時候必須再以迴圈找出精確的位置。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Ch01 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String raw[];
int len, n[], x;
Ch01() throws Exception
{
while(true){
raw=br.readLine().split(" ");
len=raw.length;
n=new int[len];
for(int i=0; i<len; i++)
n[i]=Integer.parseInt(raw[i]);
x=Integer.parseInt(br.readLine());
int index=Arrays.binarySearch(n, x);
if(index>=0)
{
if(index>0)
{
while(true)
{
index--;
if(n[index]!=x)
{
index++;
break;
}
}
}
}else
{
index=index*-1-1;
}
System.out.println(index);
System.out.println();
}
}
public static void main(String[] args) throws Exception {
new Ch01();
}
}
/*
0 1 2 3 4 5 6 7 8 9 10
1 3 6 6 6 6 6 6 6 7 8
6
1 3 6 6 6 6 6 6 6 7 8
5
1 3 6 6 6 6 6 6 6 7 8
1
*/
複製代碼
作者:
駱顗安
時間:
2022-4-18 19:04
本帖最後由 駱顗安 於 2022-4-18 19:10 編輯
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;
public class P1 {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t,n,c,s,l,k[];
String raw[];
boolean b;
ArrayList<Integer> al=new ArrayList<Integer>();
P1() throws Exception{
raw=br.readLine().split(" ");
n=raw.length;
k=new int[n];
for(int i=0;i<n;i++) k[i]=ip(i);
t=Integer.parseInt(br.readLine());
int index=Arrays.binarySearch(k, t);
if(index<0) index=-index-1;
else {
while(index>0&&k[index-1]==t) index--;
}
System.out.println(index);
}
int ip(int y) {
return Integer.parseInt(raw[y]);
}
public static void main(String[] args) throws Exception {
new P1();
}
}
複製代碼
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2