Binary Search

[stark zodiac]

When I search for most things it says not found even though my movie_list is sorted correctly, is my binary search wrong?

    
    Movie* MovieTicketMaster::FindMovie(string target_movie){
    Movie* p_movie = nullptr;
    int top_index = DEFAULT_MOVIE_COUNT -1;
    int bot_index= 0;
    int middle_index = (top_index-bot_index)/2;
    
    while(bot_index <= top_index){
        middle_index = (top_index-bot_index)/2;
        if(movie_list[middle_index].get_movie_name() == target_movie){
            p_movie = &movie_list[middle_index];
            break;
        }
        if(movie_list[middle_index].get_movie_name().compare(target_movie) > 0){
            bot_index = middle_index +1;
        }
        if(movie_list[middle_index].get_movie_name().compare(target_movie) < 0){
            top_index = middle_index -1;
        }
    }
    return p_movie;
    }
```c++

[quick hare]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[stark zodiac]

rest of code if that helps

[stark zodiac]

i found a logic error in the binary search but still doesnt work as expected:

Movie* MovieTicketMaster::FindMovie(string target_movie){
    Movie* p_movie = nullptr;
    int top_index = DEFAULT_MOVIE_COUNT -1;
    int bot_index= 0;
    int middle_index = (top_index-bot_index)/2;
    
    while(bot_index <= top_index){
        middle_index = (top_index-bot_index)/2;
        if(movie_list[middle_index].get_movie_name() == target_movie){
            p_movie = &movie_list[middle_index];
            break;
        }
        if(movie_list[middle_index].get_movie_name().compare(target_movie) > 0){
            top_index = middle_index -1;
        }
        if(movie_list[middle_index].get_movie_name().compare(target_movie) < 0){
            bot_index = middle_index +1;
        }
    }
    return p_movie;
    }

[daring trellis]

are you sure your comparison function works? and it's giving >0 and <0 when expected?

[stark zodiac]

I think thats what's wrong because my code isnt working as intended

but im not sure how to fix it

i even swapped where bot index and top index is and that didnt work eithee

so idrk

[daring trellis]

you're moving the top index down when the comparison is greater

seems backwards

[stark zodiac]

if movie[middle] is > target that means target index is < middle

no?

[daring trellis]

might want to step through with a debugger and watch your indices, compare them to the list to make sure it's going right

[stark zodiac]

alr

[swift scaffold]

The primary problem is that you are using DEFAULT_MOVIE_COUNT, which is 0, you should be using the actual count to calculate the top, otherwise, it's not searching anything.

Also, as stated, you should step through with a debugger, for example, onlinegdb, which isn't super great, but at least it's setup free and sharable: https://onlinegdb.com/P2uwXOIP-

[stark zodiac]

omg i meant to make it MOVIE_LIST_SIZE

setting it to 7 (the last index of where the movies are), the code just stops

where does it say why?

[swift scaffold]

It should have some output at the bottom

[stark zodiac]

?

oh it says this

[swift scaffold]

SIGINT is that it is interrupted. Likely because of the infinte loop I was trying to alude to

You should set a breakpoint inside your Search function, and pay special attention to the bottom, middle, and top indexes

[stark zodiac]

where else would i break if not where i found input? And maybe ur saying that since my middle is 7-0/3.5 which gets casted down is a problem, so i should do whatever middle is now +1?

[swift scaffold]

You should break during your middle calculation

[stark zodiac]

then the loop always gets skipped?

[swift scaffold]

What did you change your function to?

[stark zodiac]

this is what i ahve

[swift scaffold]

It shouldn't be skipped:

[stark zodiac]

im confused is that not the first iteration which so would be fine?

[swift scaffold]

Pay close attention to where middle, bottom and top are in relation to each other on the second iteration

[stark zodiac]

oh middle stays 3

which it shouldnt

what iuf i update middle in the if statement?

[swift scaffold]

The problem isn't where you update, but your calculation itself

[stark zodiac]

wait what\

its not (top-bot)/2?

[swift scaffold]

I just realized I stopped one step to early in the video, this should give more context, as to why your calculation is missing something

[stark zodiac]

but this is what we want here no?

or do we want to round up and not down...?

in which case i add 1

[swift scaffold]

Again, middle is smaller than bottom

[stark zodiac]

oh LOL

[swift scaffold]

You need to add something to your equation, wink wink

[stark zodiac]

i feel like ur making it super obvious

and i still cant tell 🤣

gimem as ec

i got this

[stark zodiac]

omg

i got it

its middle_index = (top_index+bot_index)/2;

idk in what world i thought the avg of 2 numbers is 1 minus the other

@swift scaffold last error, how can i use debugger to check why a decontrutor was called

[swift scaffold]

You can put a breakpoint in the destructor and “step out”

[stark zodiac]

better question, how do i make sense of what they say...

cuz this says that it was called, and ik that but dont know why

[swift scaffold]

You have to press start at the bottom

[stark zodiac]

what am i looking for

[swift scaffold]

At the top right, you have the call stack which is a list of function calls that lead to where you are

[stark zodiac]

but its the first one xD

[swift scaffold]

The current function is always the top of the stack, but where it’s called from is underneath, and where that was called underneath that, etc

[stark zodiac]

ah

[swift scaffold]

Maybe how you got there was a bit of a over-simplification on my end

[stark zodiac]

but it saying only init and bubble sort was called

and they dont delete anything

just move

[swift scaffold]

The problem is that you need one movie for the swap, which is getting destroyed - from the previous question

You may actually need to implement 2 levels of pointers using Movie** and new Movie, or save all the properties of the first movie, copy, and then set all properties of the second movie with the saved values

[stark zodiac]

and thats the way I dont get that object destroyed

everything else seems to work

[swift scaffold]

The Movie temp gets destructed at the end of the function, according to CPP RAII

[quick hare]

cppreference.com

RAII

[stark zodiac]

u can only set pointers to null or nullptr right?

is there an object null?

[swift scaffold]

You should only use nullptr in C++, NULL is C; but you can also set pointers to new <Type>, which constructs a new movie object on the heap

[stark zodiac]

ok ty

[swift scaffold]

Though be sure to remember to delete your pointers when your MovieManager goes out of scope, otherwise they stay on the stack and you have a memory leak

[quick hare]

@stark zodiac Has your question been resolved? If so, type !solved :)

[stark zodiac]

!solved