[SOLVED] Binary Search Program in C, to find the nearest value?

xpress_embedo · Jan 18, 2015

Hello!! Everyone, i have to find a particular entry from an array, i am testing this code on Code::Blocks.
My array will be of 1000 bytes but for testing purpose i am doing test on 100byte array.

I have to find the index of the searched element but with the following thing in it also, let me explain by giving an example.
Suppose my entries in array are as follow:-
array[88] = 461;
array[89] = 471;

Then when i search 461 i will get 88 but when i search 462 then i should get 88 as return value and 1 as fraction value, so that i can assume it as 88.1

I am not able to calculate the fractional part, here is my program.

Code C - [expand]
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
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
// ADC Count Values, for temperature, index = temperature
const int adcCountToTempLookUp[101] =
{
    0,5,10,15,20,25,30,35,41,46,51,56,61,66,71,76,82,87,    //18
    92,97,102,107,113,118,123,128,133,138,144,149,154,159,164,170,175,180,
    185,191,196,201,206,212,217,222,227,233,238,243,248,254,259,264,270,275,
    280,285,291,296,301,307,312,317,322,328,333,338,344,349,354,360,365,370,
    376,381,386,392,397,402,280,413,418,423,429,434,439,445,450,455,461,466,
    471,477,482,487,493,498,503,508,514,519,524
};
 
 int BinarySearch(int Value,char *fraction);
 
int main()
{
    int value;
    char fraction=0;
    while(1)
    {
        cout << "Enter the Value to Search?" << endl;
        cin >> value;
        int temperature = BinarySearch(value,&fraction);
        printf("\n\n\nTemperature = %d.%d\n\n\n",temperature,fraction);
    }
    return 0;
}
 
int BinarySearch(int Value,char *fraction)
{
    int first, last, middle;
    first = 0;
    last = 101-1;
    middle = (first+last)/2;
 
    while(first <= last)
    {
        if ( adcCountToTempLookUp[middle] < Value )
        {
            first = middle + 1;
        }
        else if ( adcCountToTempLookUp[middle] == Value )
        {
            *fraction = 0;  // Value Matched
            return middle;
        }
        else
        {
            last = middle - 1;
        }
        middle = (first + last)/2;
    }
 
    if ( first > last )
    {
        int step = adcCountToTempLookUp[middle+1]-adcCountToTempLookUp[middle];
        *fraction = (Value-adcCountToTempLookUp[middle])%step;
    }
    return middle;
}

Please help.
The difference between two array elements is not same.

xpress_embedo · Jan 18, 2015

Solved.
Simple thing, i don't how i was not able to solve that simple.

Code C - [expand]
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
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
// ADC Count Values, for temperature, index = temperature
const int adcCountToTempLookUp[101] =
{
    0,5,10,15,20,25,30,35,41,46,51,56,61,66,71,76,82,87,    //18
    92,97,102,107,113,118,123,128,133,138,144,149,154,159,164,170,175,180,
    185,191,196,201,206,212,217,222,227,233,238,243,248,254,259,264,270,275,
    280,285,291,296,301,307,312,317,322,328,333,338,344,349,354,360,365,370,
    376,381,386,392,397,402,280,413,418,423,429,434,439,445,450,455,461,466,
    471,477,482,487,493,498,503,508,514,519,524
};
 
 int BinarySearch(int Value,char *fraction);
 
int main()
{
    int value;
    char fraction=0;
    while(1)
    {
        cout << "Enter the Value to Search?" << endl;
        cin >> value;
        int temperature = BinarySearch(value,&fraction);
        printf("\n\n\nTemperature = %d.%d\n\n\n",temperature,fraction);
    }
    return 0;
}
 
int BinarySearch(int Value,char *fraction)
{
    int first, last, middle;
    first = 0;
    last = 101-1;
    middle = (first+last)/2;
 
    while(first <= last)
    {
        if ( adcCountToTempLookUp[middle] < Value )
        {
            first = middle + 1;
        }
        else if ( adcCountToTempLookUp[middle] == Value )
        {
            *fraction = 0;  // Value Matched
            return middle;
        }
        else
        {
            last = middle - 1;
        }
        middle = (first + last)/2;
    }
 
    if ( first > last )
    {
        int diff = adcCountToTempLookUp[middle+1]-adcCountToTempLookUp[middle];
        *fraction = (Value-adcCountToTempLookUp[middle])*10/diff;
    }
    return middle;
}

[SOLVED] Binary Search Program in C, to find the nearest value?

xpress_embedo

Advanced Member level 4

xpress_embedo

Advanced Member level 4

Similar threads

[SOLVED] Binary Search Program in C, to find the nearest value?

xpress_embedo

Advanced Member level 4

xpress_embedo

Advanced Member level 4

Similar threads

Privacy & Transparency

Privacy & Transparency