binary search with arrays?
Why would you use a binary search with an array when an array is direct access, would that not make the search slower? The way I am thinking about it, is with direct access you know exactly the location of where it data is stored, but with the binary search, you would still need to do, if not extremely lucky, a few searches? Am I misunderstanding this?
If you want to search for a value (not an index) in an array you can step through and compare each element until you find the value that you are looking for. This is called linear search.
If the values are stored in sorted order you can instead use binary search which usually requires fewer comparisons.
If the values are stored in sorted order you can instead use binary search which usually requires fewer comparisons.
If you know the exact location of the item, it is on par with a (perfect) hash table or 'lookup table' concept, and you simple fetch the data, you do not 'search' for it at all. This is what you describe, but not all data is this handy unfortunately.
If you have data that is sorted but you do not know anything else about it (beyond its type, like string or number) and the user asks for the record keyed by number 1234 you can...
1) look at 1 million entries one by one to see if it is there (linear)
or
2) look at about 20 entries to see if it is there (binary search). (2^20 is about a million, and because of cutting in half each time its tied to the powers of 2 (via logs)).
think of binary search like looking for the word "fubar" in a dictionary. You flip to the middle and land in the Ms, grab the front half and go half way, and get the H's, cut the front half again and land in the E's ... go half way between E and H and get F, then split the Fs the same way ... until you find the word. That is a binary search. A linear search is to check every word from aardvark to fubar.
If you have data that is sorted but you do not know anything else about it (beyond its type, like string or number) and the user asks for the record keyed by number 1234 you can...
1) look at 1 million entries one by one to see if it is there (linear)
or
2) look at about 20 entries to see if it is there (binary search). (2^20 is about a million, and because of cutting in half each time its tied to the powers of 2 (via logs)).
think of binary search like looking for the word "fubar" in a dictionary. You flip to the middle and land in the Ms, grab the front half and go half way, and get the H's, cut the front half again and land in the E's ... go half way between E and H and get F, then split the Fs the same way ... until you find the word. That is a binary search. A linear search is to check every word from aardvark to fubar.
Last edited on
oh ok I think i get it now. So say I had a hash table that was created using an array, and the bucket number was the array index number, I could just access that directly by using the hash function and getting the bucket number. But if it was just an array of numbers, i would have no way of knowing what number was stored where, so would still need to search for it in the array.
Topic archived. No new replies allowed.