UVa 10474 Where is the Marble?
簡化后題目的意思是 輸入n個整數，代表大理石編號；再輸入q個數（編號），問是否有這個編號的大理石，位置在哪里？
以下是我的代碼：
#include<stdio.h>
#include<algorithm>
using namespace std;
int binary_search(int *sorted_seq, int seq_length, int keydata)
{
int low = 0, mid, high = seq_length - 1;
while(low <= high)
{
mid = (low + high)/2;
if(keydata < sorted_seq[mid]) high = mid - 1;
else if(keydata > sorted_seq[mid]) low = mid + 1;
else
{
for(int i = mid; ; i--)
{
if(sorted_seq[i] != keydata) return (i + 2);
}
}
}
return -1;
}
int main(int argc, char const *argv[])
{
int N, Q, keydata, cnt = 0;
int seq[10005] ={0};
while((scanf("%d %d", &N, &Q) != EOF)&&(N || Q))
{
printf("CASE# %d:\n",++cnt);
for(int i = 0; i < N; i ++)
{
scanf("%d", &seq[i]);
}
sort(seq, seq+N);
for(int j = 0; j < Q; j ++)
{
scanf("%d", &keydata);
int result = binary_search(seq, N, keydata);
if(result == -1) printf("%d not found\n", keydata);
else printf("%d found at %d\n", keydata, result);
}
}
return 0;
}
一直是wrong answer，很難受，搞不懂為什么
在網上找了一份代碼，我也運行了，accepted。卻看不出來代碼和我的有什么區別。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int num[maxn] = { 0 };
// 二分查找
int found(int q, int a[], int N) {
int high = N - 1, low = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == q) {
// 找到后再向前找到第一個出現的位置
for (int i = mid; ; i--) {
if (a[i] != q) {
return i + 2;
}
}
}
else if (a[mid] > q) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
int main() {
int N, Q;
int C = 1;
while (cin >> N >> Q && N) {
for (int i = 0; i < N; i++) {
cin >> num[i];
}
sort(num, num + N);
int q;
cout << "CASE# " << C << ":" << endl;
C++;
for (int i = 0; i < Q; i++) {
cin >> q;
int pos = found(q, num, N);
if (pos == -1) {
cout << q << " not found" << endl;
}
else {
cout << q << " found at " << pos << endl;
}
}
}
}
哪位大神幫一下我？
uj5u.com熱心網友回復：
1、mid = (low + high)/2; 在第12行，有可能會發生溢位正確代碼： mid = low + (high - low) / 2;
2、第17行
for(int i = mid; ; i--)
{
if(sorted_seq[i] != keydata) return (i + 2);
}
i有可能會小于0
正確代碼：
int i = mid;
while (i-- >= 0) // code
{
if (array[i] != find) { return mid - (mid - i) + 1; }
}
另外附上一份自己寫的代碼
#include <stdio.h>
#include <algorithm>
// 二分查找 找到回傳在陣列第一次出現的位置，否則回傳-1
int found(int find, int* array, int size)
{
int low = 0, high = size - 1, mid; //置當前查找區間上、下界的初值
while (low <= high) {
mid = low + (high - low) / 2;
int cur = array[mid];
if (cur > find) //向前查找
{
high = mid - 1;
}
else if (cur < find) //向后查找
{
low = mid + 1;
}
else //找到
{
int i = mid;
while (i-- >= 0) // code
{
if (array[i] != find) { return mid - (mid - i) + 1; }
}
}
}
return -1;
}
int main()
{
const int array_size = 100;
int array[100] = {0};
//獲取用戶要輸入的數字的數量
int count;
for (;;) {
printf("請輸入數字的數量(1-%d)：", array_size);
if (scanf("%d", &count) && count >= 1 && count <= 100) { break; }
else {
printf("請輸入正確的數量：\n");
}
}
//讀取用戶輸入，保存的陣列array中
int i = 0; //記錄當前輸入數字的數量
for (;;) {
printf("請輸入%d個數字：", i + 1);
if (scanf("%d", &array[i])) { i++; }
if (i >= count) {
printf("輸入完成！");
break;
}
}
int find;
printf("請輸入要查找的數字：");
for (;;) {
if (scanf("%d", &find)) { break; }
else {
printf("你輸入的不是數字，請重新輸入");
}
}
//查找之前先進行排序
std::sort(array, array + count);
int ret = found(find, array, count);
if (ret < 0) { printf("未找到！"); }
else {
printf("您查找的數字位置在第%d個\n", ret + 1);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/17496.html
標籤：基礎類
上一篇：查詢水果價格