I have a file containing about 30K songs names. I have to use this list for automatic text suggestion with AJAX. Some of the names also start with numbers. My question is can I do binary search over this list ? If yes, how ?
5
-
Define "binary search", please. How do you want the results to look like? Is is a dropdown?silkfire– silkfire2013-07-21 19:49:25 +00:00Commented Jul 21, 2013 at 19:49
-
4Use a database... don't try doing this with that big of a file.Orangepill– Orangepill2013-07-21 19:51:26 +00:00Commented Jul 21, 2013 at 19:51
-
@silkfire Yes, its will show as in drop down like in Googlesilverflash– silverflash2013-07-21 19:53:13 +00:00Commented Jul 21, 2013 at 19:53
-
@Orangepill text search from database are much slowersilverflash– silverflash2013-07-21 19:53:39 +00:00Commented Jul 21, 2013 at 19:53
-
2How do you figure...I would like to see benchmarks showing this.Orangepill– Orangepill2013-07-21 19:55:17 +00:00Commented Jul 21, 2013 at 19:55
Add a comment
|
2 Answers
First of all sort the list;
Suppose, the first letter the user has typed is "A";
Start with high = 0 and low = number of strings -1;
Then you can define a high and a low index where high is the last index that starts with "A" and low is the first index that has a string starts with "A". With two binary searches this can be achieved.
So if the next letter typed is say "B" then you make another binary search in the range high and low defined above and adjust the high and low again with two binary searches. Make sure you search for the second character of the strings between high and low to be matched with "B" and so on :)
Note: I'd suggest to use Database to do so, but as you queried if there's any way to use binary search, I'm answering this way :)
Simple sql query: SELECT column_name FROM table_name WHERE column_name LIKE 'prefix%' to select strings those start with 'prefix' stored in the column 'column_name' of 'table_name' table
8 Comments
Orangepill
Big fall down here is you have to populate and search an array of 30,000 elements with each request.
Fallen
@Orangepill: the list is pre populated I believe. and the search is binary search so lg(30,000)<=16 (where, lg = log2) So there'll be at most 16+16=32 comparisons at each step.
silverflash
Won't I have to query database every time a user will press a key, if I will use database ?
Orangepill
@Fallen in mysql keys are represented by default as a binary tree. Do your big O notation there and take out the performance impact of having to read in the array and sort it
Fallen
@Orangepill: Please note that I've added a note to my answer. I also suggest to use database(I've created similar functionality using Database) but my answer is only to show that it's possible with binary search. even if he had asked it in algorithm section I'd add how to solve this using trie :)
|
You could use mixed array_search ( mixed $needle , array $haystack [, bool $strict = false ] )
