0

I can't figure out what I'm doing wrong. My algorithm works for smaller arrays, but once the number of values increases, the program stops and I have to hit Ctrl + C. I thought maybe it was an issue with my sort algorithm, but it seems to check out. Help?

int low=0;
int high=n-1;
while (low<=high)
    {     
    int mid=(high-low)/2;
    if (value==values[mid])
    {
        return true;
    }
    else if (value<values[mid])
    {
        high=mid-1;
    }
    else
    {
        low=mid+1;
    }  
}
return 0;

2 Answers 2

0

When C divides integer by integer it truncates the value (remove all numbers after the decimal point), so


int 19 / int 10 = 1 (not 1.9!)


Due to this rule and according to your mathematical equation, mid = (high - low) / 2

let us assume that we have a list [5, 6, 7, 8], n = 4 , high = 3, low = 0 and let's assume the value we are searching for is 8

at the 1st iteration:

    mid = (3 - 0) / 2 = 1
    value > values[mid], 8 > 6 then
    low = mid + 1 = 2

on the 2nd iteration:

    mid = (3 - 2) / 2 = 0
    value > values[mid], 8 > 5 then
    low = mid + 1 = 1

Do you see? low is decreasing instead of increasing, if we continue to the 3d iteration we will find something not good.

on the 3rd iteration:

    mid = (3 - 1) / 2 = 1    // mid has become 1 again! look at the first iteration   
    value > values[mid], 8 > 6 then
    low = mid + 1 = 2       // we back to iteration 1, we are trapped in the loop!

So clearly this mathematical equation is not the right solution, this equation is called the average Slope of a linear function (with 2 units base), no need to talk about that.

Anyway to find the average you need to ADD your high and low values and divide them by 2, so you have to use this equation

mid = (high + low) / 2

The General formula to find the average number:

Avg = (x1 + x2+ x3 + x4 + .... + xn) / n

At the end, what will the program do when the value you search for does not exist in the array? i think you should keep this condition in mind.

I hope I helped.

0

There are many things to be worked on here. See this code snippet

int mid=(high+low)/2; // ...first
while (low<=mid) // ...second
{     
    mid=low + (int)((high-low)/2);  // ...third
    if (value==values[mid] || value==values[mid+1]) // ...fourth
    {
        return true;
    }
    else if (value<values[mid])
    {
        high=mid;  // ...fifth
    }
    else
    {
        low=mid;  // ...sixth
    }  
}
return false; 
  1. Wrong Formula : (high-low)/2 should be replaced by low + (high-low)/2
  2. Test condition can be either low <= mid or mid <= high, but not low <= high, because that goes to infinite loop as we haven't updated the values of high or low in such a way that low becomes greater than high or high becomes less than low. This difference can't be spotted unless it is sure that the element to be searched is in the array. If the element to be searched won't be in array, then high will be forever equal to low and loop shall never terminate. See this.
  3. Similar to first one. Although I typecasted, but that won't make a difference(here).
  4. Automatic type casting will work as a floor function, so you will never ever get access to some indices, for example, in an array of 3 elements if the desired value is stored at last index, then mid = (1+3)/2 = 2 then low = mid = 2 then mid = (2+3)/2 = 2(typecasted from 2.5). So its better to confirm such cases with value==values[mid+1].
3
  • Ah... I don't know why I used high-low. But changing it to high+low fixed it. Re: #2-4, I'm not sure I understand what you mean by type casting. And I haven't changed the test condition yet, but it hasn't gone into infinite loop. Why will low <= high go into infinite loop? I interpreted it as basically to continue until there is no range to check -- but why is low<=mid or mid<=high okay, and not the one above? Sep 22, 2014 at 15:48
  • I have also changed the values that you update for high = mid and low = mid, but still I am searching for the reason why not high = mid -1 and low = mid + 1.
    – sinister
    Sep 22, 2014 at 15:52
  • Answer edited, also see this
    – sinister
    Sep 22, 2014 at 16:04

You must log in to answer this question.

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