Binary Dictionary Search

[Raknarg]

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:

Turing:

fcn dic_indexing (s : string, list : array 1 .. * of string) : boolean     var place : int     place := upper (list) div 2     var upperList : array place + 1 .. upper (list) of string     var lowerList : array lower (list) .. place - 1 of string

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?

[DemonWasp]

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).

[Raknarg]

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)

[Raknarg]

thanks, I fixed it

[DemonWasp]

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.

[Raknarg]

haha well I did always know Turing was a dumb language thanks anyways, I used your solution