Archived

This topic is now archived and is closed to further replies.

Balanced search algo problems

This topic is 5017 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, this sounds idiotic, but I can''t figure out a way to fix my balanced search algoritm. It either places the data on the wrong position or it crashes. I am kinda hopeless now, so any help is appreciated. It utilizes MFC''s CList. Here it goes:
void CUserTimeTable::Add(time_t tmTime)
{
    POSITION Pos;
    size_t nIndex = 0;
    size_t nCount = 0;
    size_t nStep  = 0;

    nCount = m_TimeList.GetCount();
    nIndex = nCount / 2;
    nStep  = nCount / 2;
    bool bFound = false;
    
    while (nStep != 0)
    {
        Pos = m_TimeList.FindIndex(nIndex);
        time_t t = m_TimeList.GetAt(Pos);
        TRACE("Index: %d; Step: %d; Value: %d\n", nIndex, nStep, t);
        if (t < tmTime)
        {
            nIndex += nStep;
            nStep /=  2;
        }
        else if (t > tmTime)
        {
            nIndex -= nStep;
            nStep /= 2;
        }
        else // Item found

        {
            bFound = true;
            break; 
        }
    }

    if (!bFound)
        m_TimeList.InsertAfter(Pos, tmTime);

    TRACE("Dumping TimeTable list for debug purposes\n");
    for (int i = 0; i < m_TimeList.GetCount(); ++i)
    {
        TRACE("\tEntry %d: %d\n", i, m_TimeList.GetAt(m_TimeList.FindIndex(i)));
    }
}
Toolmaker
-Earth is 98% full. Please delete anybody you can.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
give us input and output (of the debug prints)

Share this post


Link to post
Share on other sites
I randomly filled the list during the constructor, so I have a few items already in there. So, here it goes:

TimeTable.Add(25);
TimeTable.Add(47);
TimeTable.Add(80);

Called code ^


Index: 4; Step: 4; Value: 79
Index: 0; Step: 2; Value: 10
Index: 2; Step: 1; Value: 46
Dumping TimeTable list for debug purposes
Entry 0: 10
Entry 1: 45
Entry 2: 46
Entry 3: 25
Entry 4: 48
Entry 5: 79
Entry 6: 103
Entry 7: 175
Entry 8: 201
Index: 4; Step: 4; Value: 48
Index: 0; Step: 2; Value: 10
Index: 2; Step: 1; Value: 46
Dumping TimeTable list for debug purposes
Entry 0: 10
Entry 1: 45
Entry 2: 46
Entry 3: 47
Entry 4: 25
Entry 5: 48
Entry 6: 79
Entry 7: 103
Entry 8: 175
Entry 9: 201
Index: 5; Step: 5; Value: 48 *Crashed*


Toolmaker



-Earth is 98% full. Please delete anybody you can.

[edited by - toolmaker on March 24, 2004 5:01:05 AM]

Share this post


Link to post
Share on other sites
At the last add you begin with index 5.
Because the value is smaller than the value you want to add you do:
nIndex += nStep; // nIndex = 5 + 5
That makes 10 and you don't have a 10th entry.


[edited by - TheSorcerer on March 24, 2004 7:18:59 AM]

Share this post


Link to post
Share on other sites