1

This is an attempt at binary search. n is the user input (from main script).

This code compiles but doesn't find the needle in the haystack. I'm a bit lost and would welcome assistance.

bool search(int value, int values[], int n)
{

int min = values[0];
int max = values[n-1];
int mid = (max + min) / 2;

if (n >= 0)
{


    if (values[mid] == value)
    {
        return true; 
    }

    else if (values[mid] > value)
    {
        for (int i=0; i < (values[mid])-1; i++) //to search left half
        {
            if (i == value)
            {
                return true;
            }
        }
    }

    else if (values[mid] > value)
    {
        for (int i = (values[mid])+1; i < (values[max])-1; i++)   
        //search right half
        {
            if (i == value)
            {
                return true;
            }
        }
    }
    else
    {
        return false;
    }
}    
return false;
}
1

When you write

int min;
int max;

you're creating two int variables, but their value is undefined, it's the value that happened to be at that place in memory when they were created.

You don't assign anything to them, so they remain in that undefined state.

Then you write

int mid = (max + min) / 2;

calculating a value from two undefined values.

Also, binary search requires some kind of loop. Maybe review it before writing an implementation.

| improve this answer | |
  • I changed those variables to this: int min; int max; int mid = (max + min) / 2; It's now throwing the errors that max and min haven't been initialized when they were used in the last part (int mid = (max + min) / 2;). I thought that they were initialized in the 2 lines above that. – Android1 Mar 29 '17 at 13:13
  • Should the extra loop be ' while(max>=min) ' as an outside loop or something like that? – Android1 Mar 29 '17 at 13:25
  • "initialisation" is the first assignment after declaring a variable. If it's not a global variable, the value is undefined until that point, and you should not use its value anywhere. min and max should be indices, not values. After initialisation of min and max, there should be one loop (like the while(max>=min) you suggested), and inside, after calculation of mid, some if-else or if-elseif-else structure, no other loops. – Blauelf Mar 29 '17 at 13:31
  • I don't understand what to do. I'm new to all this. Can't I define the mid-point like this : int mid = (max + min) / 2; ? Also how can I define Max and Min as variables here when they change? – Android1 Mar 29 '17 at 13:37
  • int min = 0; int max = n - 1; provide initialisation together with the declaration. Those are initial values, you'll change them inside the loop. Keep in mind that min, max, and mid are indices, and never values. – Blauelf Mar 29 '17 at 14:19
2

Actually what you had written is not a binary search as in each move its not changing the size of array to half of original size. By the way mistake in your code is in line no. 19 and 30 as you are writing

min = 0; max = n - 1;

(values[mid])-1 which is wrong, it should be mid - 1 (line 19)

(values[mid])+1 which is wrong, it should be mid - 1 (line 30)

| improve this answer | |
  • So do you mean it should be (values[mid-1]) for both of them or get rid of values part and brackets? Also, the reason I put plus for that one is that the array was to be searched from 1 to the right of the mid-point if the value sought was to the right of the mid-point - as in searching from the middle (plus 1) to the end. I thought we had to do that. – Android1 Mar 29 '17 at 13:20
  • I've changed the code but I gather it still needs another loop. What loop would you suggest and where would you suggest I add it? I tried a 'while' loop outside but that didn't work (crashed system - infinite loop). – Android1 Mar 30 '17 at 4:13
  • I removed the iterations and it seems to work better. It's finding the ints in the searches now. Thanks. – Android1 Mar 30 '17 at 9:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .