How binary search works in real world scenario?
In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers.
But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?
Please explain in detail with a small example if possible.
algorithms search-algorithms binary-search
asked Dec 2 at 7:00
Raj
1183
add a comment |
In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers.
But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?
Please explain in detail with a small example if possible.
algorithms search-algorithms binary-search
asked Dec 2 at 7:00
Raj
1183
9
Binary search has nothing to do with integers. It applies to any ordered domain. I’m not sure where you got this misconception from.
– Yuval Filmus
Dec 2 at 7:06
In a sense, you are right: in a real computer, all data boils down to integers with some limits (as strings of bits). But algorithms per se usually don't have such restrictions.
– Kirill Bulygin
Dec 2 at 16:14
“Is the data converted and stored in some numeric format?” Well, yes. Computer memories only store bits, everything else is defined by data formats "we" invented. You might want to check out how encodings such as ASCII work.
– Andrea Lazzarotto
Dec 4 at 17:34
add a comment |
In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers.
But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?
Please explain in detail with a small example if possible.
algorithms search-algorithms binary-search
asked Dec 2 at 7:00
Raj
1183
In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers.
But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?
Please explain in detail with a small example if possible.
algorithms search-algorithms binary-search
algorithms search-algorithms binary-search
asked Dec 2 at 7:00
Raj
1183
asked Dec 2 at 7:00
Raj
1183
asked Dec 2 at 7:00
Raj
1183
asked Dec 2 at 7:00
Raj
1183
asked Dec 2 at 7:00
Raj
1183
1183
9
Binary search has nothing to do with integers. It applies to any ordered domain. I’m not sure where you got this misconception from.
– Yuval Filmus
Dec 2 at 7:06
In a sense, you are right: in a real computer, all data boils down to integers with some limits (as strings of bits). But algorithms per se usually don't have such restrictions.
– Kirill Bulygin
Dec 2 at 16:14
“Is the data converted and stored in some numeric format?” Well, yes. Computer memories only store bits, everything else is defined by data formats "we" invented. You might want to check out how encodings such as ASCII work.
– Andrea Lazzarotto
Dec 4 at 17:34
add a comment |
9
Binary search has nothing to do with integers. It applies to any ordered domain. I’m not sure where you got this misconception from.
– Yuval Filmus
Dec 2 at 7:06
In a sense, you are right: in a real computer, all data boils down to integers with some limits (as strings of bits). But algorithms per se usually don't have such restrictions.
– Kirill Bulygin
Dec 2 at 16:14
“Is the data converted and stored in some numeric format?” Well, yes. Computer memories only store bits, everything else is defined by data formats "we" invented. You might want to check out how encodings such as ASCII work.
– Andrea Lazzarotto
Dec 4 at 17:34
9
9
Binary search has nothing to do with integers. It applies to any ordered domain. I’m not sure where you got this misconception from.
– Yuval Filmus
Dec 2 at 7:06
Binary search has nothing to do with integers. It applies to any ordered domain. I’m not sure where you got this misconception from.
– Yuval Filmus
Dec 2 at 7:06
In a sense, you are right: in a real computer, all data boils down to integers with some limits (as strings of bits). But algorithms per se usually don't have such restrictions.
– Kirill Bulygin
Dec 2 at 16:14
In a sense, you are right: in a real computer, all data boils down to integers with some limits (as strings of bits). But algorithms per se usually don't have such restrictions.
– Kirill Bulygin
Dec 2 at 16:14
“Is the data converted and stored in some numeric format?” Well, yes. Computer memories only store bits, everything else is defined by data formats "we" invented. You might want to check out how encodings such as ASCII work.
– Andrea Lazzarotto
Dec 4 at 17:34
“Is the data converted and stored in some numeric format?” Well, yes. Computer memories only store bits, everything else is defined by data formats "we" invented. You might want to check out how encodings such as ASCII work.
– Andrea Lazzarotto
Dec 4 at 17:34
add a comment |
1 Answer
1
active
oldest
votes
As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.
At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.
You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.
Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.
Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.
I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?
Hope this helps!
EDIT: Edited to say "Prof. Filmus..." as that is more formal.
answered Dec 2 at 7:26
Benny Profane
962
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f100858%2fhow-binary-search-works-in-real-world-scenario%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.
At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.
You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.
Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.
Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.
I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?
Hope this helps!
EDIT: Edited to say "Prof. Filmus..." as that is more formal.
answered Dec 2 at 7:26
Benny Profane
962
add a comment |
As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.
At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.
You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.
Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.
Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.
I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?
Hope this helps!
EDIT: Edited to say "Prof. Filmus..." as that is more formal.
answered Dec 2 at 7:26
Benny Profane
962
add a comment |
As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.
At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.
You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.
Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.
Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.
I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?
Hope this helps!
EDIT: Edited to say "Prof. Filmus..." as that is more formal.
answered Dec 2 at 7:26
Benny Profane
962
As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.
At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.
You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.
Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.
Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.
I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?
Hope this helps!
EDIT: Edited to say "Prof. Filmus..." as that is more formal.
answered Dec 2 at 7:26
Benny Profane
962
answered Dec 2 at 7:26
Benny Profane
962
answered Dec 2 at 7:26
Benny Profane
962
answered Dec 2 at 7:26
Benny Profane
962
962
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f100858%2fhow-binary-search-works-in-real-world-scenario%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
9
Binary search has nothing to do with integers. It applies to any ordered domain. I’m not sure where you got this misconception from.
– Yuval Filmus
Dec 2 at 7:06
In a sense, you are right: in a real computer, all data boils down to integers with some limits (as strings of bits). But algorithms per se usually don't have such restrictions.
– Kirill Bulygin
Dec 2 at 16:14
“Is the data converted and stored in some numeric format?” Well, yes. Computer memories only store bits, everything else is defined by data formats "we" invented. You might want to check out how encodings such as ASCII work.
– Andrea Lazzarotto
Dec 4 at 17:34