UVa 10474 Where is the Marble?
Simplified title mean input n integers, representing the marble number; To enter qq number (number), ask whether there is the number of marble, where is the location?
Here is my code:

 
#include 
#include 

using namespace std; 

Sorted_seq int binary_search (int * and an int seq_length, int keydata) 
{
Int low=0, mid, high=seq_length - 1; 

While (low & lt;=high) 
{
Mid=+ high (low)/2; 
If (keydata & lt; Sorted_seq high/mid)=mid - 1; 
Else if (keydata & gt; Sorted_seq low/mid)=mid + 1; 
The else 
{
For (int I=mid; ; I -) 
{
If (sorted_seq [I]!=keydata) return (I + 2); 
} 
} 
} 
return -1; 
} 
Int main (int arg c, char * const argv []) 
{
Int N, Q, keydata, CNT=0; 
Int seq [10005]={0}; 
While ((the scanf (" % d % d ", & amp; N, & amp; Q)!=(EOF) & amp; & (N | | Q)) 
{
Printf (" CASE# % d: \ n ", + + CNT); 
for(int i=0; i {
The scanf (" % d ", & amp; Seq [I]); 
} 
Sort (seq, seq + N); 
For (int j=0; j {
The scanf (" % d ", & amp; Keydata); 
Int result=binary_search (seq, N, keydata); 
If (result==1) printf (" % d not found \ n ", keydata); 
The else printf (" % d found at % d \ n ", keydata, result); 
} 
} 
return 0; 
} 

Has been a wrong answer, very afflictive, don't understand why
Got a code on the net, I also run, accepted, but don't see the code and I have what distinction,

 # include & lt; Iostream> 
#include  

using namespace std; 

Const int maxn=10005; 

Int num={0} [maxn]; 

//binary search 
Int found (int q, int a [], int N) {
Int high=N - 1, low=0; 
While (low & lt;=high) {
Int mid=+ high (low)/2; 
If (a/mid==q) {
//find forward to find the location of the first appeared again after 
For (int I=mid; ; I -) {
If (a [I]! Q)={
Return the I + 2; 
} 
} 
} 
Else if (a/mid & gt; Q) {
High=mid - 1; 
} 
The else {
Low=mid + 1; 
} 
} 
return -1; 
} 

Int main () {
Int N, Q; 
Int C=1; 
While (cin & gt;> N & gt;> Q & amp; & N) {
For (int I=0; i Cin & gt;> Num [I]; 
} 
Sort (num, num + N); 
Int q; 
Cout & lt; <"CASE#" & lt; C + +; 
For (int I=0; i Cin & gt;> q; 
Int pos=found (q, num, N); 
If (pos==1) {
Cout & lt; } 
The else {
Cout & lt; } 
} 
} 
} 

What a great god to help me?

CodePudding user response:

1, mid=+ high (low)/2; In line 12, is likely to be an overflow
The correct code: mid=low + (high - low)/2;
2, line 17
For (int I=mid; ; I -)
{
If (sorted_seq [I]!=keydata) return (I + 2);
}
I could be less than 0

The correct code:
Int I=mid;
While (I - & gt;=0)//code
{
If (array [I]! Find)={return mid - (mid - I) + 1; }
}

Also enclose a copy of their written code
#include
#include

//binary search to find back to appear for the first time in the array, otherwise return 1
Array int found (int the find, int * and an int size)
{
Int low=0, high=size 1, mid;//on the current search interval and lower bound of the initial value
While (low & lt;=high) {
Mid=low + (high - low)/2;
Int cur=array (mids);
If (cur & gt; Find)//forward lookup
{
High=mid - 1;
}
Else if (cur & lt; Find)//look behind
{
Low=mid + 1;
}
The else//find
{
Int I=mid;
While (I - & gt;=0)//code
{
If (array [I]! Find)={return mid - (mid - I) + 1; }
}
}
}

return -1;
}

Int main ()
{
Const int array_size=100;
An int array [100]={0};
//get the user to input the number of digital
Int count;

For (;; ) {
Printf (" please enter the number (1 - % d) : the number of ", array_size);
If (the scanf (" % d ", & amp; The count) & amp; & The count & gt;=1 & amp; & The count & lt;=100) {break; }
The else {
Printf (" please input the correct number: \ n ");
}
}

//read the user input, save the array in the array
int i=0;//record the number of the current input digital
For (;; ) {
Printf (" please enter the Numbers: % d ", I + 1);
If (the scanf (" % d ", & amp; Array [I]) {i++; }
If (I & gt;={count)
Printf (" input complete!" );
break;
}
}
Int the find;
Printf (" please enter a number to find: ");
For (;; ) {
If (the scanf (" % d ", & amp; Find)) {break; }
The else {
Printf (" you input is not number, please enter again ");
}
}

//sorted before you find
STD: : sort (array, the array + count);

Int ret=found (the find, array, count);
If (ret & lt; 0 {printf () "is not found!" ); }
The else {
Printf (" you find digital position in the first % d \ n ", ret + 1);
}

return 0;
}