haha well I did always know Turing was a dumb language
thanks anyways, I used your solutionComputer Science Canada Binary Dictionary Search |
| Author: | Raknarg [ Thu Mar 22, 2012 1:04 pm ] | ||
| Post subject: | Binary Dictionary Search | ||
So just for fun in my compsci class, im making a recursive function to quickly search through a large array with a binary search. However I'm encountering a problem here:
It gives me errors at array place + 1 and array lower (list), and tells me they must be known at compile time. However, I can't think of any way to get around that. And personally, I dont see the issue in the first place. Any ideas? |
|||
| Author: | DemonWasp [ Thu Mar 22, 2012 1:13 pm ] |
| Post subject: | RE:Binary Dictionary Search |
You shouldn't have to make new arrays for a binary search (which will be seriously slow for large arrays, and prohibitively slow and costly for huge arrays). Your method should accept a range (low, high) to look in; it should start with (lower(list), upper(list)) and then when you recurse you'll do so with either (low,mid) or (mid,high). |
|
| Author: | Raknarg [ Thu Mar 22, 2012 1:18 pm ] |
| Post subject: | RE:Binary Dictionary Search |
Fair enough. My original idea was just to include the range within the parameter upon caling itself, but then I realized I was thinking of strings and not arrays, which I dont think you can do the same with :/ like with strings you can call s (1 .. 5) but with arrays you cant just call a (1 .. 5) |
|
| Author: | Raknarg [ Thu Mar 22, 2012 1:28 pm ] |
| Post subject: | RE:Binary Dictionary Search |
thanks, I fixed it |
|
| Author: | DemonWasp [ Thu Mar 22, 2012 1:33 pm ] |
| Post subject: | RE:Binary Dictionary Search |
With arrays in a LOT of nicer languages, you can pull out subsections. C and C++ let you do this by pointer arithmetic, while higher-level languages like Python use constructs almost exactly like what you list: array(3:5) is elements #3 through #5 of the array. Even in languages where you can do that, it may be faster to use the solution I discussed above. Certainly it won't be any slower, unless you do silly things like passing the contents of the array by value. The reason you can't use run-time bounds for your arrays is a Turing-specific compiler / interpreter limitation and doesn't exist in any other language I'm familiar with. |
|
| Author: | Raknarg [ Thu Mar 22, 2012 1:35 pm ] |
| Post subject: | RE:Binary Dictionary Search |
haha well I did always know Turing was a dumb language thanks anyways, I used your solution |
|