# Binary search algorithm only works for smaller arrays

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;
``````

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.

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]`.
• 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`. Sep 22, 2014 at 15:52
• Answer edited, also see this Sep 22, 2014 at 16:04