That binary search code is deceptive, which is what makes it look like the linear search you've already written - you've seen the for/next loop, but it's the bits in the middle that are important.
Your search starts at the beginning of the array and steps forward until it finds a match - in 1000 items, where the item you are searching for exists, you will average 500 checks per deletion.
Binary search is a relatively simple concept:
You start with a sorted array, and 2 markers - one marker indicates the first item (let's call it 'low'), and the other the last item ('high').
You calculate a point in the exact middle of those two markers, and determine whether the item you are looking for is below that point, or above that point, or an exact match. If's it's an exact match, then you are done. If it is in the lower half, you reset 'high' to the middle point, otherwise you reset 'low' to the middle point - repeat until your low and high points match, and that's the insertion point.
In 1000 items, you will find an exact match in 10 or less checks.
Here's an example using strings:
dim SearchArray(20) as string
` Prepare an initial array - don't need to do this, an empty array works fine too
for i=0 to 20
SearchArray(i) = chr$(i + 65)
next i
repeat
` Read a new string
read InsertString$
if InsertString$ <> ""
` Find the insert position
Position = BinarySearch( InsertString$, 1 )
` If it's past the end of the array, append
if Position > array count( SearchArray() )
array insert at bottom SearchArray()
else
` Otherwise, insert
array insert at element SearchArray(), Position
endif
` Set the new item
SearchArray(Position) = InsertString$
endif
until InsertString$ = ""
` Display the array contents
for i=0 to array count( SearchArray() )
print i, " - ", SearchArray(i)
next
wait key
end
` Some data to insert
data "@ Insert at the front"
data "Z Insert at the end"
data "G Somewhere in the middle"
data " Insert at the front again"
data "H"
data "I"
data ""
function BinarySearch(Target as string, Nearest as integer)
local High as integer
local Low as integer
local Middle as integer
` Set the Low and High points outside of the array
Low = -1
High = array count( SearchArray() )+1
` Loop while the difference between them is above 1 (ie, they have not passed or matching)
while High - Low > 1
` Pick a mid-point
Middle = (High + Low) / 2
` Test to see if the item is below the target value
if SearchArray(Middle) < Target
` If it is, move the low point to the mid-point
Low = Middle
else
` Otherwise, move the high point to the mid-point
High = Middle
endif
endwhile
` If not looking for a best match, then need to do some further checking
if Nearest = 0
` If the high-point is still beyond the end of the array, exit with a 'not found'
if High > array count( SearchArray() ) then exitfunction -1
` If the item currently pointed to by the high-point is not the one, exit with a 'not found'
if SearchArray(High) <> Target then exitfunction -1
` At this point, we have an exact match
endif
endfunction HighQuote: "rechecking objects"
I mean exactly what you've stated. Using a random starting point, and then checking from there is a reasonable thing to do - in fact my own plug-ins did the same thing until I came across a much better method (which you can't duplicate easily).
The point is that if instead of starting from a random point each time (in your hopefully massively reduced range of object id's), it's actually better to NOT use a random start point, but instead to remember where you stopped searching last time and continue from that point, wrapping back to id 1 when you hit the end of your range (if you impose that kind of limit).
The standard function I see, pretty much all of the time, is this:
function FindFreeObject1()
local i as integer
i = 1
while object exist(i) = 1
inc i
endwhile
endfunction i
Calling this code when you have 0 objects and are creating 1000 objects will result in the OBJECT EXIST() function being called 500,500 times.
A better method is this:
#constant MAX_OBJECT_ID = 1000
global NextFreeObject as integer = 0
function FindFreeObject2()
local i as integer
if NextFreeObject < 0 or NextFreeObject > MAX_OBJECT_ID then NextFreeObject = 1
for i = NextFreeObject to MAX_OBJECT_ID
if object exist(i) = 0
NextFreeObject = i + 1
exitfunction i
endif
next
if NextFreeObject > 1
for i = 1 to NextFreeObject
if object exist(i) = 0
NextFreeObject = i + 1
exitfunction i
endif
next
endif
endfunction 0
... which follows the method I described earlier. Using the pattern of 'load everything, delete everything, repeat', it will tend to find a free object id on the very first call of OBJECT EXIST(). Even when randomly deleting items, it will eventually hit runs of free objects, and then revert to single OBJECT EXIST() calls.
Of course, the very best is the FIND FREE OBJECT() function from my plug-ins
