Saturday, 17 July 2010
Totem
Creep
I wanna have control
I want a perfect body
I want a perfect soul
I want you to notice
when I'm not around
You're so fuckin' special
I wish I was special
But I'm a creep
I'm a weirdo
What the hell am I doin' here?
Thursday, 1 July 2010
Binary Search
low = 0
high = N
while (low <>
mid = (low + high) / 2
if (A[mid] <>
low = mid + 1;
else
//can't be high = mid-1: here A[mid] >= value,
//so high can't be <>
high = mid;
}
// high == low, using high or low depends on taste
if ((low <>
return low // found
else
return -1 // not found
It feels perfect, looks perfect even the Prof in your class must have written the same, then why am I talking about it. Well ,it has a major bug which had stayed undetected like for ever and detected sometime very recently. (Google for more details and timeline)
Problem: Well line 4 says, mid=(high+low)/2.Say if "high" is the highest integer your compiler can access and if low is any number greater than zero then mid goes out of range and causes overflow problems. :O :O
Solution: Do (high/2 +low/2) or low+(high-low)/2
Come to think of it: While implementing many other array based divide and conquer algorithms like merge sort etc, we do the same to get to the center of the array.
Caution :Don't take the average.
