Binary Search

Scorpius (3)
Hello everyone! I have to solve a problem using binary search, but i am not sure i wrote the code corectly. Here it is:

It is given a sorted array, having N numbers and M questions:
0:Find out the highest position of an element having the value x or return -1 if the value does not exist in the array;
1:The highest position of an element <=x;
2:The lowest position of an element >=x.

Here is an exemple of file containing the array, and the value of x:
cautbin.in
5
1 3 3 3 5
3
0 3
1 3
2 3

Can you please tell me what is wrong with my implementation?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
#include <iostream>
#include <fstream>

using namespace std;

int v[100001], N, M, mij, x, nr;

int cautare0(int k, int inf, int sup)
{
    int p=-1;
     while (inf<=sup)
        {mij=inf+(sup-inf)/2;
         if (v[mij]==k) 
             {p=mij;
              inf=mij+1;}
         else     
            if (v[mij]<k) 
               inf=mij+1;
            else 
                sup=mij-1;} 
    return p;                               
}

int cautare1 (int k, int inf, int sup)
{
    int p=0, q;
    while (inf<=sup)
       {mij=inf+(sup-inf)/2;
        if (v[mij]<=k)
           {q=k-v[mij];
            p=mij;
            if (k-v[mij+1]>q)
                sup=mij-1;}
        else
            inf=mij+1;} 
    return p;                                        
}

int cautare2 (int k, int inf, int sup)
{
    int p=0, q;
    while (inf<=sup)
       {mij=inf+(sup-inf)/2;
        if (v[mij]>=k)
           {q=v[mij]-k;
            p=mij;
            if (v[mij+1]-k>=q)
                sup=mij-1;}
        else
            inf=mij+1;}    
    return p;                                                 
}   

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>N;
    for (int i=1; i<=N; i++)
         f>>v[i];
    f>>M; 
    for (int j=0; j<M; j++)
       {f>>nr>>x;
        if (nr==0)        
              g<<cautare0(x,1,N);      
        if (nr==1)      
              g<<cautare1(x,1,N);
        if (nr==2)     
              g<<cautare2(x,1,N);}
    f.close();
    g.close();          
    return 0;         
}


Last edited on
JMan (10)
I have absolutly no idea what are you trying to do. Please explain
Scorpius (3)
Well, i think in the first function it's quite obvious that i am testing the value comparing it with the element int the middle of the array, then move to the wright half, find out the new middle etc.

For the next two functions, i thought i could use pretty much the same algorythm as in the first one. The only difference is that i have to find out which element is closer to the value of a given number x. That's why i must constantly have the subtraction v[mij]-k (or k-v[mij]). Due to that, the program should know which half it shoud be verified first.

That's my idea, but i don't think it's correct enough. So if you notice something wrong, i would appreciate if you could help me. This assignment is driving me crazy!
JMan (10)
first: Format it when ur posting so it will be easier for everyone to read :D
second: Whats the error log? try to understand what it says.
third: I think you are trying to find the highest position of an value x. in that case, just run through the array and it will be easier.
four: put comments beside the code, reading without comments is nightmare as we have no idea why something is performed (sometimes i cant even understand my code without those comments)
Scorpius (3)
I am sorry for making it difficult to read.

As i said before, i need to use binary search. This is the assignment.
I loaded the problem on a site and the error is time limit excedeed. I have no idea what i did wrong.
Topic archived. No new replies allowed.