Thread: Binary search

I'm doing binary search. It's working, but it's jumping over the sorting part, it leaves the vector unsorted. I don't understand why. This is the code

Code:

#include <stdio.h>
#include <conio.h>

int main()
{
    int a[10], i, j, x, n, inf, supp, mid, M=0;
    printf("How many elements does your vector have?\n");
    scanf("%d", &n);
    printf("What are those elements?\n");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("What value do you need to find?\n");
    scanf("%d", &x);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[i] < a[j])
            {
                M = a[i];
                a[i] = a[j];
                a[j] = M;
            }
        }

    }
    for (i = 0; i < n; i++)
    {
        inf = 0;
        supp = n;
        mid = (inf + supp) / 2;

        if (x > mid)
            inf = mid + 1;
        else
            supp = mid - 1;
    }
    printf("The value your are searching for is on position %d\n", mid);
    getch();
}

It appears to be sorting when I run the program. Perhaps you should print the sorted array before your search.

Also you really should validate the number of elements entry to insure the user enters ten or less to avoid possible array overruns.

Actually it's still not working propperly

What seems to be the problem?

Jim

I printed the sorted array and modified some things and it seems to be working fine now but I'm still not sure. I received an error after it worked one time but I accidentally closed it before reading it. Other than that I have no errors and It's working. I'm hoping it's fine. This is the code. Thank you for your response.

Code:

#include <stdio.h>
#include <conio.h>

int main()
{
    int a[10], i, j, x, n, inf, supp, mid, M = 0, flag=0;
    printf("How many elements does your vector have?\n");
    scanf("%d", &n);
    printf("What are those elements?\n");
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("What value do you need to find?\n");
    scanf("%d", &x);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[i] < a[j])
            {
                M = a[i];
                a[i] = a[j];
                a[j] = M;
            }
        }

    }
    printf("your sorted vector is:\n");
    for (i = 0; i < n; i++)
        printf("%d\n", a[i]);
    printf("\n");
    flag = 0;
    inf = 0;
    supp = n;
    while (flag == 0 && inf <= supp)
    {

        mid = (int)((inf + supp) / 2);
        if (x == a[mid])
        {
            printf("the value you seek is at position: %d", mid);
            flag = 1;
        }
        else
        if (x > a[mid])
            inf = mid;
        else
            supp = mid;
    
    }
    
    getch();
}

Originally Posted by jimblumberg

It appears to be sorting when I run the program. Perhaps you should print the sorted array before your search.

Also you really should validate the number of elements entry to insure the user enters ten or less to avoid possible array overruns.


What seems to be the problem?

Jim

What do you mean by "validate the number of elements entry"? How can I do that?

You have a very small array, you need to make sure the user is only allowed to enter the number of elements to fill that array, no more. So you need to check to insure the user doesn't enter a value for 'n' that is larger than the size of the array. By the way you really should consider more meaningful variable names.


Jim

What happens if somebody search for a value that is not in the array?

I was trying to put an

Code:

if (flag ==0)
{
     printf("these are not the droids you are looking for\n");
}

but it's not working because I don't know where to put it exactly.

Originally Posted by OctavianC

I was trying to put an

Code:

if (flag ==0)
{
     printf("these are not the droids you are looking for\n");
}

but it's not working because I don't know where to put it exactly.

You have to figure out when your while-loop has chewed through all elements without finding the value. You have two cases of done. Done as in "I found the value and it is at this position" and done as in "The value was not in the array at all".

I have no idea I tried putting it everywhere in the while, even outside. I think there's something wrong with the code itself.

Originally Posted by OctavianC

I have no idea I tried putting it everywhere in the while, even outside. I think there's something wrong with the code itself.

Where you put something is not the question, the question is what you put there?

Exactly what conditions have to be full filled for you to know that you cannot find the value you are looking for?

tried putting it everywhere in the while, even outside. I think there's something wrong with the code itself.

Yes there is a problem with your code. If you search for an item that is not in your array the program goes into an infinite loop, the program never ends.

When will inf ever be equal to or less than supp?

Using meaningful variable names would probably go a long way to help you understand the logic of this program.

What do the variable names inf and supp actually refer to?

Jim

Originally Posted by jimblumberg

What do the variable names inf and supp actually refer to?

inf = inferior (lowest value in the vector)
supp = supperrior (highest one)

To me inf stands for infinite, supp == supplemental. What about x?

What about the more important question, the actual cause of the problem? "When will inf ever be equal to or less than supp?"


Also note you don't need that cast on line 37, all the variables are int so the result will also be an int without the cast.

Jim

Originally Posted by jimblumberg

What about the more important question, the actual cause of the problem? "When will inf ever be equal to or less than supp?"
Jim

Always?