❔ Applying binary search into my project
I need help with implementing binary search in this project
https://gist.github.com/Programmer-Faraj/fdc814033943b69af8bdf19a00b83b14
Gist
This is an assignment project from my course
This is an assignment project from my course . GitHub Gist: instantly share code, notes, and snippets.
330 Replies
to copy from #help-0
StringComparer Class (System)
Represents a string comparison operation that uses specific case and culture-based or ordinal comparison rules.
?
Thanks a lot, I'll go head and modify the current pattern of the Binary search, so it does the search alphabetically. But before I do that I have a question for you.
Hey again, are you available?
you got a question, ask it
you'll hear back tomorrow 
Ok! Awesome. Thank you guys a lot.
seems like we have different timezones, I'm from Sweden btw.
In order to apply Binary search alphabetically, I would need to convert char to a number since the first letter of each word represents a char, so how do I go and do that?
why do you think you need to convert a char to a number?
binary search just needs a sorted array, as long as the values are sortable you can use them directly
Oh! Really. I though I should convert first, because my values are strings in a list and not numbers.
what do you need numbers for?
to find the index of each char I guess
or maybe I'm wrong
how would binary search find the element if they're a collection of strings
because binary search depends on sorting
you can sort anything as long as you can compare the elements
Aha! Ok! Wow, I didn't touch into more deeply in this topic, but I learned something now.
I guess the same context follows for strings as well as for integers, except I need to use the compare method instead
I mean, that is pretty much what he's doing. That's what
StringComparer.Compare() does. Takes in two strings and spits out a number that you can use for sorting.but that's not what he was asking
ah, fair enough
I didn't read closely enough
Oh! Stupid me 🤦♂️
since I'm using the Compare() method, why the hell I've been thinking about converting a char to a number then 😆
exactly 
Logical thinking is very great skill and I'm missing it unfortunately 🙆🏻♂️
But guys, why I'm getting those errors above?
wait a minute this is the issue
var middle = (left + right) / 2;because you're trying to return an
int when the methods specifies it returns a stringconsider what the number means and what you actually want to return from the method
Ok! I see what you mean.
Ok! That's a bit hard to figure out actually.
how so?
I don't know
I mean the method compares and returns integer, I'm not sure why it says you can't convert int to string
because you can't
the integer isn't what you want to return, think about what that integer is in this context
what method?
what method compares and returns integer?
Ok! So the Compare() method compares the strings and the returns an inte either 0 or -1 or 1 based on the comparison in my case I'm already returning an int which's -1 which's wrong because that int should be the outcome of the method not hardcoded, makes sense?
yyyyyessss
except for the "already" part
and that's why it saying
you can't convert int to stringbecause you can't
because have written
return -1;
for a method that you declared to return stringSorry I said wrongly
I need to delete that part -1
right
or rather
replace it
the question remains, how do I go and implement the logic where when the method returns the value, I can use that method to say either "found" or "not found"
what method?
replace it with what?
you tell me
what is the scenario where that line is reached?
compare method
which one?
where you had
return -1
what is the scenario where that line of code is reachedI'm not really sure
well, let's read through the code, then
you've got a loop
with an exit condition
Yes sir
no
breaks within the loop
so
that line is reached when the loop exits on its own
without hitting that return inside the loop
what does the loop do?
functional descriptionWell! The loop will keep looping until a certain condition matches then it stops looping.
what condition?
what can cause that loop to exit
NOT counting the
return inside the loop, cause then it will skip over the return at the end of your methodeither by break or false value
yes, but there is no
break
when does "false" value" occur?no
when invalid input is entered or when the comparison outputs to -1
uhhh, no
when the comparison outputs
-1, you hit the else clause inside the loopyes
the default else
which just changes the bounds of your loop
er
rather
the bounds of the data slice you're looking at
alternatively
it changes one of the two data items you're comparing
what keeps the loop going?
Sorry for being away, I had to take a break just to relax my brain.
You mean the last else?
yes
I mean, it's the only one
Ok
by data items you mean comparing the two strings?
yes
That's a bit complicated, the loop should continue looping based on the return of the comparison.
yes
and when will it exit?
there's a 5-word answer
yes, that is the documentation for the return value of
.Compare()
when does your loop exitit should exist when the output is -1?
no
No wait
assuming "the output" means "the return value of .Compare()"
when the it finds the element and returns zero 0
what returns 0?
the compare METHOD
okay
well, .Compare() doesn't find anything
and I asked about the loop, not .Compare()
when does the loop exit
Aha! You're right. The while loop is not depending on the Compare method, it doesn't say compare tell me what to do? should I loop or not? Rather the while is controlling the method inside.
it goes both ways
the while loop invokes the method
and the method does affect the loop, because it's used to sometimes perform a
return
which breaks the loop
you tell me
when does the loop exit
don't know?
well
what does the loop DO?
what is its purpose?
why'd you write it?I mean the loop should exist when it's returning
when your
BinarySearch() method is returning, yes
when elseI mean from what learned is that if you want to stop a while loop, there are several ways you can accomplish this step.
either you set a bool value true or false
nnnnnot really, no
a loop will exit when you call
break or return within it
or when it begins a new iteration and its condition is false
a while loop, at leastor if you iterate to 10 then it will stop at number 10
depends on how you write it
yes, I was gonna mentioned these too
not "too"
those are the ways a loop can exit
Yes either by break or return
Is the
while loop the problem, or a lack of understanding of what "binary search" is and does?right now the problem is that he was trying to
return -1; from .BinarySearch() and didn't know whyRight.
I'm pretty new to Binary search
so, we're trying to figure out what the scenario is where the loop exits and reaches the
return line at the end of .BinarySearch(), so we can decide what it SHOULD return instead of -1
ultimately, yeah, it's a problem of not knowing enough about the binary search algorithm
or at least, the implementation of it that he's written
he wrote a loop and can't tell me what it's supposed to do
or when it's supposed to exitwill I did find out that it was wrong to return -1 but still didn't know what should I use to exist the loop until you told me that the keyword
break is the only optionI said nothing of the sort
lets rewind a step. what is the purpose of a search method?
nor did I say that you should be exiting the loop
what are the possible "cases" of its results?
I'm not asking you to touch the loop at all
I'm asking you to explain what it does
or what you intend it to do
maybe it's correct, maybe not
what should it be doing
when should it exit
I'm pretty bad at logical thinking
right, that's why we're working on it
You guys have gone many stuff and solved a lot of complicated problems but not me at least not yet.
absolutely
But you guys teach me a lot on how to think like a programmer and that's awesome
You guys don't give me the full answer, but you teach me where and why I'm doing wrong.
So, what is the purpose of a search method? What is the intended goal of calling
var result = BinarySearch(list, element);?
what do we hope to get out of itGood question
The method is doing the the looping, comparing and by invoking the method in side a switch statement we are able to add the method to the manu + use those arguments passed by parameters and then use the calling method to take user input for searching.
Not at that detail. Think bigger pocture
Sorry, guy! I reply when I get a short breaks from my work.
Pocture
picture
like, what does a search method do
what is its purpose
You mean this one?
No, your method
YOUR binary search method
I think they're trying to ask what value you want from your method
I'd like him to reach that conclusion himself
Yeah sorry
thanks 🙂
Maybe try asking what they intend to do with the method
Yes, the method should search & find the value of the element in the list.
find the value of the element in the list.the value is the element
Sorry, that's correct.
So what should it find and return?
Of course it should find the element that's sorted by the Bubble sort algorithm.
no, what stop
so if a search method isnt looking for a value, what is it looking for?
what does it return?
If the list is not sorted then it can't find the sorted element
sorted element????? an element cant be sorted a list can but thats not what Im asking
Sorry
I'm asking, what should the method return
the answer is NOT "the sorted element" or "the value of element"
if you dont know the term we use for it, you can describe what it is instead
This sounds like my chatgpt threads
it should return an int either 0 or 1 or -1
no.
what
thats what
Compare does.Yes
we are not talking about compare
we are talking about
BinarySearchOk
what should this print?
The index of the element of course
There we go. The index.
And what if the element I'm searching for isnt in the list?
Since this is what we use Binary or Linear or Quick search for
Other wise what's the meaning of using thses algorithms
I don't understand what you are trying to say. Yes, search algorithms try to find the index of the given item, thats literally their purpose.
And what I've been trying to get you to realize the entire day.
So, now that you know what you want your method to do, I hope it will be easier to understand the code.
For example, when would it be appropriate to
return -1; in a search method?Awesome question
Let me make a logical point here from my understanding
We can use this keyword when we're searching for int and not string
why?
First
What keyword?
why not string?
when we're dealing with searching numbers and we pass a int parameters in out method, and when the method doesn't find the element then we should be using return -1 if the element is not found.
we should be using return -1 if the element is not found.
thats true, regardless of if you are seraching for ints or strings
-1 for an index means "not found"Really
yes really
why would it matter if you are searching for ints, strings or
Cakes?
its still a list of T and you are trying to find the index-1 isn't mean the index is out of boundaries
-1 isnt a valid index, thats correct
But here is my question
but what else should you return from a method that should return an index, when there was no hit?
0 and any positive number is a valid index, so we cant return that
That's a good question
no its not
the answer is "return -1"
thats true for all index returning methods
they always return -1 to say "failed" or "not found" etc
Ok
I suppose you could throw an exception too, if you really wanted, but imho not a good idea
Yeah! That's correct, this is what I learned from the tutorials too.
Ok
But we couldn't return -1 when we had the Compare() method
sure we can. Those are not related
it says you can't convert int to string
Because compare returns 0 1 -1 an int
... yes?
how is that related to the return value of the search method?!
Man there's a lot of logic in this dame Binary search and it's just a few lines of code 🤷🏻♂️
Programming is logic
thats all it is.
Good question
What question?
100% correct
This
That's not a question...
Well
Kinda a question
well, it is - a rhetorical question.
I didnt ask it expecting an answer.
Ok
the obvious answer is "they are not"
But I wondered too
anyways
What does a binary search do? We know it wants to return the index of the given element
but whats special about binary search?
because both our method signature and Compare() both returns, but our signature can return multiple data types, but not Compare()
but our signature can return multiple data types, but not Compare()WHAT
You can return int bool string
no?
no you cant
But Compare() returns int
public static int BinarySearch(List<string[]> haystack, string needle)
thats the signature for binary search
(in your case)
you cant return bool, or string
it should return an index(!!!)
a bool isnt an indexOh! I'm not talking specifically Binary search.
a string isnt an index
I'm talking generally about the signature
... you are talking generally about any method written by you?
I know the Binary search returns only index
Faraj, please, this is getting beyond frustrating.
Can you STICK TO THE TASK AT HAND
stop going of on your weird tangents, focus on trying to implement binary search
yes like public bool MyBool() public string MyMethod() public int Deposit() and so on...
Why are you talking about that now?
how is that relevant to your search method?
Yes, sorry 🤗
so again.. what is the trick behind binary search? what does it do?
it started from when you talked about returning method
nevermind
It compares & searches for the element and returns the index of that element
when it finds it
well, thats what any search method does
whats special about binary search?
good question
it splits the list in half by comparing and it compares either on the left or right of the middle
yes!
not like Linear search where it iterates through the whole list until a match is hit
Binary search is effective and fast compare to the Linear
Think about if we have a million items in database
how long will it take for the Linear search to iterate and find the target
... you dont need to "sell" binary search
Okay, so we know how binary search works and what it should return
So when we compare two values for the purpose of binary searching, we use
Compare
and it returns one of -1, 0, 1Binary search it does a good job by splitting the halve million elements and gets easier and easier to search
Focus!
Yes
I do
Last warning
hahaha
Can you post your current search code?
Of course I can
why do you have
string as the return value?because I'm searching for an element type string
If I was searching for numbers it would've been int
Oh really?
I thought we agreed that it should return the index of the element
not the element itself
Oh 🤦♂️
Honestly it kinda feels like nothing we say sticks
I have to say the same thing 200 times
I had a bad sleep last night, I may seem stupid to you. But my brain is not functioning well.
I explain in great detail why and you say "Ah yes, of course!" and then its gone the next second
Sorry for messing up sometimes
It's just I'm not so used to complicated stuff yet
Im sorry to say that this isn't complicated stuff...
types, return types, methods is... the foundational stuff
for you not for me it involves many stuff
But that doesnt mean this is complicated in terms of programming.
This is the basics.
Nevermind. Lets look at the code.
First, why are you doing two comparisons?
But I know these concepts are less complex compare to advanced stuff
comparing values is the expensive part of a search algorithm, and you shouldn't need to compare more than once in a single cycle
Ok
Well! The reason why I used both is because I was replacing these comparings.
you only need one.
okay, so, we know Compare can return three different values
positive, negative or zero
yeah, but thats not using a
Compare method.Yes
the comparions are however the same, we just need to call them slightly differently
Ok
Thanks a lot for teaching me this part
so, you can use two
ifs and an else to do this, as above..
but I think its a lot cleaner with a switch
also, you should probably use StringComparer.OrdinalIgnoreCase.Compare instead of string.CompareBut when we apply Binary search in a list of integers, then we're using multiple comparisons for middle left and middle right, so in my case you mean we're doing both in one single method?
Ok! We go with the switch approach then.
What's the different then?
I think its time you start googling
because you can compare integers directly for a 1,0,-1 result, you cant with strings
quick search rofl
Ok!
How come you pick this one instead of the Compare() aren'r both for comparing strings and returning an int?
strings are way more complicated than they seem
its not a huge difference, you can use either for now and it likely wont cause issues..
Ok! Interesting to know.
Great
I created the switch statement now
you have already implemented the switch statement yesterday for my other project https://discord.com/channels/@me/998900826280042536/1100312126905663589
show it
why are you pulling an individual character out of your string?
wait
why is that a list of string arrays?
Although this algo implemented for integer values
faraj...
thats my code
thats literally the code I sent you two days ago
Yes
I didnt mean for you to show me MY code
I meant for you to show your code.
I don't see any character in the code
List<string[]> haystack why is this like this?because the assignment is insane
i missed the actual requirements i guess
they dont allow classes and force them to use string arrays to represent blog posts
gross
so it's "fine," it's just that the first element is the title or something?
Yeah! Because this was required for me to use based on the assignment description.
yes
this is why i stopped pursuing higher education
Really, do they do it in the uni too.
i mean my college courses weren't much better but at least they introduced classes
Ok! Here is my code.
Ok! Well! I guess it's different from school to school.
why is it still returning a string?!
I actually give up
I don't want to help anymore
I haven't write any code for the switch yet, we can go through it together.
Take it easy man, I missed to remove it. It's not like I have written it on purpose.
It's totally alright for me
I don't understand how this much confusion has arisen from a simple binary search
Do you call this a simple Binary search, are you kidding with me?
Binary search is relatively simple, yes
Seeming as it is just coding an algorithm
I know it's just one basic context that you can apply the same principle for all projects, but implementing it to a list of strings using the Compare() or the String.Comparer() method made it a bit complicated.
Just a bit of documentation to read
I mean it's not that you just copy paste or write code and that's it, there are some things you need to learn in order to implement the algo.
I am reading the docs currently
StringComparer Class (System)
Represents a string comparison operation that uses specific case and culture-based or ordinal comparison rules.
What the hell, there are many Compare methods not just one.
would you be able to offer some help?
With?
Also you may want to check if the list is sorted before trying to binary search
Wait I just realised its a list of type string array, why is that
Have you been able to understand and implement the int version from scratch?
the project models blog posts as string arrays because classes are too complicated i guess
external requirement
so whatever part of the post is in the first element of the array is what's being searched for
Thank you guys for showing up, I really appreciate.
Yes, it is sorted. By Bubble sort.
above you can see the project that I have built so far without the Binary search that got me so much headache
Yes, I think it's easier than applying to a strings.
There's a ton of resources & tutorials and ther're all using dame a list of integers, bu tnot strings.
that's why he's asking if you fully understand it, because the concept is practically the same here
you're just using a different strategy to compare the elements
nothing else changes
I totally agree with you man. I'm not stupid, I can learn stuff, although I've five hours of sleep for the last two years and my brain is not very clear, but I hate giving up, I like coding, but it feels complicated sometimes not always.
You mentioned something very interested here
Using a different strategy is what makes it a bit hard for me to understand why? How? and so on...
Plus this Compare() or String.Comparer() or ToCompare() this is hard for me to implement all alone that's why I need your help
I mean this docs makes a bit clear to understand https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.icomparer-1.compare?view=net-8.0#system-collections-generic-icomparer-1-compare(-0-0)
IComparer.Compare(T, T) Method (System.Collections.Generic)
Compares two objects and returns a value indicating whether one is less than, equal to, or greater than the other.
basically you have two strings (variable x, variable y) and you can compare these two
it sounds like you may want to spend time thinking about how to break problems down into smaller problems
once you get good at that it's a lot easier to adapt solutions to new problems because it becomes a matter of swapping out the parts that change and leaving everything else alone
also, get more sleep because 5 hours a night isn't enough
Ok! I see your point.
works for me! 
My problem is just applying the Compare() method for binary search alphabetically that's all
alphabetically?
compare already compares alphabetically, you don't even have to be concerned with that
that's why the process of comparing strings is abstracted behind a Compare method
all you need to care about is that Compare tells you if a string is "less than" "more than" or "equal to" another string
Sorry, I meant strings.
Sorry man, I remember you told me yesterday that I don't need to convert any char or search alphabetically, I meant applying Binary search to strings.
okay
where we at with that?
from what you had yesterday, it seemed you were well on-track
can you guys explain this line for me?
that compares the strings
x and y for orderingYeah
using the
OrdinalIgnoreCase instance of StringComparer
meaning, comparison is ordinal, meaning (I think) ignoring accent marks and shit, and case-insensitiveOk
and it returns a numeric value indicating the relative order of
x and yOk
a negative number if
x comes before y, a positive number if x coimes after y, and 0 if they are equivalentGreat explanation, thanks.
using case-insensitive comparison for
BinarySearch is maybe not a good ideaOk
it would mean if your list contains, say
"value" and "VALUE" the search algorithm won't be able to tell the difference
it could return either of them as the matchI s it because we need the case letters for our search?
the binary search algorithm is KINDA predicated on the assumption that the data you're searching doesn't contain any duplicate values
and those two would count as duplicates if you're doing case-insensitive comparison
Ok
off the top of my head, the worst-case of this is that it'll just be arbitrary with of the duplicates it returns
so, not the end of the world
but still probably doesn't make much sense
So you were right, we would need the case-sensitive for our search
unless you're being instructed not to, yeah, I would recommend that
StringComparer.Ordinal.Compare() or StirngComparer.CurrentCulture.Compare()Awesome
afaik ordinal means it essentially compares the raw values of the characters without taking any capitalization or culture into account
The StringComparer returned by the Ordinal property performs a simple byte comparison that is independent of language.
I will use this method for my search, then I would use a switch statement for the returning
so, kinda the opposite of what I guessed above
a "culture-aware" comparison would be the one that maybe treats accented characters and non-accented characters as equivalent, or nearly-equivalent
a switch would work, yeah
as would your
if/else statements from yesterdayAwesome
Guys, since I couldn't debug my project, because I'm using VS on Mac and it doesn't display the main issue when I set breakpoint. So therefore, I need to ask you guys. https://gist.github.com/Programmer-Faraj/8963d73d17e16380e1ed108758e80270
It's working well when doing the Binary search, but the issue is located where when I enter a wrong value, it still displaying the index which's weird.
if your debugger isn't working you need to figure that out
you won't always be able to ask someone to debug for you on discord
desk check your search method, run through it by hand and you'll see what the problem is
it should be really clear what's wrong, at least the thing that i'm seeing is wrong
wait...
you removed your search parameter from your method? how is that supposed to work at all?
what are you searching for?
@Faraj ^
Ok! You're right. I need to practice solving problem skill just like logical skill. I agree with you. But why did they build the debug feature in the IDE if everyone could solve problem on their own? When I have a logical problem in like Binary search only skilled people like you guys can figure out where the bug is located.
i'm sorry but this isn't even a logical problem at this point
the very first most basic step of solving a problem is knowing the inputs and the outputs
if you don't see a problem with removing the most critical input to a search function, the thing you want to find, idk how to help you
and binary search is not an algorithm that takes very much skill to understand
You're right. I missed this part. I should have passed a param and use the argument to search for the index of the list and I've done that earlier in my Linear search and I didn't pay attention 🤦♂️
that's why I was able to prompt that message of index is not found in my Linear search and in the Binary search.
You're right. I am with your opinion with all the points you mentioned. I'm terrible at reading the pattern of the code and notice what is right or wrong implemented.
I find the Binary search not complicated now as yesterday.
learning coding is not so easy. I mean sometimes I get super happy when I implement a block of code without asking for help or when I'm making progress and sometimes I get so disappointed and frustrated when I get stuck and many people give up because of imposter syndrome at least not me.
The thing is when you want to implement an algorithm or a certain block of code, I go and look at StackOverflow and I see people have implemented the same block, but in many different patterns or contexts, so it's hard to be able to understand all these patterns, but not for skilled people like you guys.
this looks like a little wtf to me
i wanted him to see that himself
because yes, that's obviously wrong
agreed
I'll modify the code and try and fix the bug
ordinal just compares the codes
I thought the
Compare() is doing this jobBingo
I was able to fix the bug yahoooo
Although, I noticed one sensitive issue.
when I used the method in this context the compiler was throwing out of range exception on this line of code.
but when I changed it to this this time the CLI freezes when inputing capital case letters like C# instead of c# I wondered why?
I think this is exactly what happens currently in my project, you were right.
The thing is if I don't use the Ignore case, then I'll have to figure out some way to apply try catch exception handling to handle the
no, you don't just throw try catches at exceptions
figure out why it's throwing an exception and decide if that means there is another problem with your code
Ok
That's a fair assumption
I think -1 is the boundary of our list
like we use this if the search algorithm tries to iterate outside the boundary of a list
am I right or wrong?
just for the sake of learning
yes, but the exception isn't being thrown at that point in the code
what does ArgumentOutOfRangeException mean on that line?
Aha! Ok! Well it says the index was out of range, it means when we tried to compare and search for the element the index of the element entered by the user is outside of the list boundary this is how I understood.
Because for me it seems to me that the issue is not that the searched index fails to hit the target or find the index of the element.
when does the user enter an index of an element?
you don't know the index of the element the user wants, that's why you're searching for it
so somehow your
middle is getting pushed outside the bounds of your list which shouldn't be allowed to happen
either that or one or more of the arrays in the list has no elementsThat is utter nonsense. Case-sensitive comparison is not causing you to get an Exception.
what fixed said: you're receiving an exception because you tried to access the list, with an index that is out-of-bounds for the list
like, maybe -1
or 2, when the list's size is 2
the index is something YOU calculated
not the user
so how did YOU come up with that index
afaik he figured this one out and moved on
:/
why make a new thread?
¯\_(ツ)_/¯
There's been multiple threads this has spanned across
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.