發表新討論
#6975: [簡答] Binary Search


saitor362320 (Kira Yamato)

學校 : 國立臺灣海洋大學
編號 : 9939
來源 : [140.121.215.219]
最後登入時間 ：
2014-09-15 21:28:39
d732. 二分搜尋法 | From: [175.181.131.112] | 發表日期 : 2012-09-03 23:11
/**********************************************************************************/
/*  Problem: d732 "二分搜尋法" from                                          */
/*  Language: CPP (682 Bytes)                                                     */
/*  Result: AC(190ms, 602KB) judge by this@ZeroJudge                              */
/*  Author: saitor362320 at 2012-09-03 22:50:18                                   */
/**********************************************************************************/


#include<cstdlib>
#include<iostream>

using namespace std;

int BinarySearch(int A[], int n, int k)
{
int l=0;
int u=n;
int m;

while(l<=u){
m = (l+u)/2;
if(k == A[m])
return m;
else if(k<A[m])
u=m-1;
else
l=m+1;
//cout << "l, m, u " << l << m << u << endl;
}
return -1;
}

int main()
{
int n, k;

while(cin>>n>>k){
int* num;
num = (int*) malloc(n*sizeof(int));

for(int i=0 ; i<n ; ++i){
cin >> num[i];
}

for(int i=0 ; i<k ; ++i){
int ask;
cin >> ask;
int ans = BinarySearch(num,n,ask);

if(ans<0)
cout << 0 << endl;
else
cout << ans+1 << endl;
}
}
return 0;
}

 
#7146: Re:[簡答] Binary Search


forever41200 (forever41200)

學校 : 臺北市立建國高級中學
編號 : 25724
來源 : [140.113.136.217]
最後登入時間 ：
2015-04-07 18:35:13
d732. 二分搜尋法 | From: [60.250.104.164, 192.168.216.7] | 發表日期 : 2012-11-03 15:53
我也解出來了^^ 
 
/**********************************************************************************/
/*  Problem: d732 "二分搜尋法" from                                          */
/*  Language: CPP (628 Bytes)                                                     */
/*  Result: AC(76ms, 981KB) judge by this@ZeroJudge                               */
/*  Author: forever41200 at 2012-11-03 15:48:53                                   */
/**********************************************************************************/


#include<iostream>
using namespace std;
int binsrch(int num[], int len, int target){
int lower = 0;
int upper = len-1;
int mid=0;
while(lower <= upper){
mid = (lower + upper) / 2;
if(target > num[mid])
lower = mid + 1;
else if(target < num[mid])
upper = mid - 1;
else
return mid + 1;
}
return 0;
}
int main(){
int len,query,i;
cin>>len>>query;
int num[len];
int target[query];
int ans[query];
for(i=0;i<len;i++)
cin>>num[i];
for(i=0;i<query;i++){
cin>>target[i];
ans[i] = binsrch(num,len,target[i]);
}
for(i=0;i<query;i++)
cout<<ans[i]<<"\n";
return 0;
}

 
ZeroJudge Forum