my binary search method in Ruby is similar to Don's. I tested with
array [1,1,2,2,2,2,3,3,9,14,14] , to which the answer should be 9,
and now added what I call "fluff" (meaningless numbers) to either:
the left (300_000 zeroes at the head) , making it difficult for direct
approach; the middle (150_000 of each of the 3's and 14's around
the 9 ); or the right (300_000 18's added to the end). I also had
it run each method 100 times. I just hope the following formats
decently...
user system total real
fluff on left
direct 16.750000 0.000000 16.750000 ( 16.753000)
binary 0.000000 0.000000 0.000000 ( 0.002000)
fluff in middle
direct 8.344000 0.000000 8.344000 ( 8.335000)
binary 6.844000 0.000000 6.844000 ( 6.846000)
fluff on right
direct 0.000000 0.000000 0.000000 ( 0.001000)
binary 0.000000 0.000000 0.000000 ( 0.003000)
As expected, the direct approach sucks when it hits a large n and the
singleton is near the end. It actually does fairly well otherwise.
By the way, Don, I took "pairs" to mean it divides 2 evenly, and the
asker even gave an example with four 2's. (Assuming his result should
be 4, not 5, typo ;P). So your line about decreasing the midpoint
just once is not enough, and actually to increase binary performance,
a check should be made if ar[mid]==ar[left] , also check if
ar[mid]==ar[right], and if it does, like in my fluff examples , you
can save loads of time on useless checks.
@surender -- good question; I would think no, but binary search would
still return 3. Direct approach would fail with default checks. I
got the impression we were searching for a single[ton].
On Aug 25, 6:32 am, surender sanke <[email protected]> wrote:
> { 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also
> comes under this problem?
>
> surender
>
>
>
>
>
>
>
> On Thu, Aug 25, 2011 at 8:12 AM, Dave <[email protected]> wrote:
> > @Shailesh: Sir, your response is unresponsive, because the original
> > poster specifically asked for a solution that was < O(n). Please don't
> > waste our time giving answers that so obviously do not meet the
> > problem statement.
>
> > Dave
>
> > On Aug 24, 6:33 pm, smb <[email protected]> wrote:
> > > XOR all the elements, the answer is the number you want.
>
> > > On Aug 24, 5:11 pm, Don <[email protected]> wrote:
>
> > > > I assume that "elements in pairs" means that each value occurs exactly
> > > > twice except for the one single.
> > > > This algorithm is O(log n) and is nonrecursive. Writing it recursively
> > > > would make it a couple of lines shorter, but because it is purely tail
> > > > recursion, that is not necessary.
>
> > > > // Given an array "a" of size elements in which all elements occur in
> > > > pairs except for one single item,
> > > > // find the single item and return its value.
> > > > int findSingle(int *a, int size)
> > > > {
> > > > while(1)
> > > > {
> > > > // For an array of size 1, the only element is the single.
> > > > if (size == 1) return a[0];
>
> > > > // The logic below won't work for size three, but it is simple to
> > > > find the single.
> > > > else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0];
> > > > else
> > > > {
> > > > // Pick the midpoint of the array
> > > > int midpoint = size/2;
>
> > > > // If we are looking at the second element of a pair, move back
> > > > to the first element
> > > > if (a[midpoint] == a[midpoint-1]) --midpoint;
>
> > > > // If midpoint is not a pair, that is the single.
> > > > else if (a[midpoint] != a[midpoint+1]) return a[midpoint];
>
> > > > // If midpoint is odd, look at left half of the array
> > > > if (midpoint % 2) size = midpoint;
>
> > > > else // If midpoint is even, look at the right half of the array
> > > > {
> > > > a += midpoint;
> > > > size -= midpoint;
> > > > }
> > > > }
> > > > }
>
> > > > }
>
> > > > On Aug 24, 4:49 am, atul purohit <[email protected]> wrote:
>
> > > > > Hi,
>
> > > > > A* sorted *integer array contains elements in pairs. All the pairs
> > are
> > > > > complete except one element whose pair is missing. Find that element.
>
> > > > > Ex. { 1,1,2,2,2,2,3,3,4,5,5}
> > > > > result = 5
>
> > > > > There is a standard solution which returns an XOR of all the
> > elements. But
> > > > > this needs O(n) time complexity. The person who asked me this
> > question said
> > > > > that this can be done in < O(n). Maybe we can eliminate some
> > elements.
> > > > > Anyone knows how to do this?
>
> > > > > Cheers,
> > > > > Atul- Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
