Modify

Opened 11 months ago

Last modified 9 months ago

#3680 new Feature Request

Improve _ArrayBinarySearch function

Reported by: anonymous Owned by:
Milestone: Component: Standard UDFs
Version: Severity: None
Keywords: Cc:

Description

Think about the binary search not found case, return -1, then we _ArrayAdd and _ArraySort again. But if the function can return a "proper" location through an additional byRef, we can now directly _ArrayInsert. The binary search has to reach this position when it confirms it should return -1, therefore there should be no additional cost. The return should keep unchanged to ensure back compatibility.

Additionally, when more than 1D involved, binary search on one column could have multiple match, a function which return the first and last match can be written reuse the binary search. However, with additional edge argument (-1 for smallest index that match, 0 for which ever index match first, 1 for largest index that match) would make it convenient. This could require a little more coding in the function.

Overall, it should be convenient to use the c style sorting functions as argument for both sort and binary search. Above requirement can be implemented by adjust sorting function when searching, at the cost of double the comparison times.

Attachments (0)

Change History (3)

comment:1 Changed 11 months ago by TicketCleanup

  • Version 3.3.14.0 deleted

Automatic ticket cleanup.

comment:2 Changed 11 months ago by Melba23

You want it - you write it. Or at least a first attempt so we can see exactly what it is you wish to see implemented.

M23

comment:3 Changed 9 months ago by BrewManNH

Additionally, when more than 1D involved, binary search on one column could have multiple match, a function which return the first and last match can be written reuse the binary search. However, with additional edge argument (-1 for smallest index that match, 0 for which ever index match first, 1 for largest index that match) would make it convenient. This could require a little more coding in the function.

We already have an _ArrayFindAll function, why do you want 2 of them?
Because the array has to be sorted for _ArrayBinarySearch to work, finding the first occurrence should make it dead simple for the programmer to be able to find the following matches, because they will all be in order.
In reference to your first paragraph, I can't say I have any understanding of what you're trying to say. If you are searching an array, why are you using arrayinsert and re-searching? You know that the entry will be there, because you just inserted it! _ArrayBinarySearch isn't intended to tell you where in an array something is, it's intended to give you the fastest way of determining if something is in the array. Yes, it will tell you where in the array it was found, but I think it's main purpose was for finding if rather than where something is.

Guidelines for posting comments:

  • You cannot re-open a ticket but you may still leave a comment if you have additional information to add.
  • In-depth discussions should take place on the forum.

For more information see the full version of the ticket guidelines here.

Add Comment

Modify Ticket

Action
as new The ticket will remain with no owner.
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.