Modify

Opened 6 years ago

Closed 4 years ago

#3680 closed Feature Request (Rejected)

Improve _ArrayBinarySearch function

Reported by: anonymous Owned by: Melba23
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 (5)

comment:1 Changed 6 years ago by TicketCleanup

  • Version 3.3.14.0 deleted

Automatic ticket cleanup.

comment:2 Changed 6 years 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 6 years 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.

comment:4 Changed 4 years ago by Jpm

  • Owner set to Melba23
  • Status changed from new to assigned

comment:5 Changed 4 years ago by Jpm

  • Resolution set to Rejected
  • Status changed from assigned to closed

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 closed The owner will remain Melba23.
Author


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

 
Note: See TracTickets for help on using tickets.