Preliminary Map.binarySearch function with tests

[reinux]

As per our discussion in fsharp/fslang-suggestions, I've written a binarySearch : 'Key -> Map<'Key, 'Value> -> ('Key, 'Value) option * ('Key, 'Value) option * ('Key, 'Value) option along with its wrapper method and a handful of tests.

This version returns a tuple of 3 options: one for the item with the closest matching key below; one for the match; and one for the item with the closest matching key above.

Several other ideas were raised in the discussion, which I think are worth considering further before committing to this shape:

• Return a DU with four cases: an exact match; a match below; a match above; and a match above or below but not exact. This would have the advantage of having only four total patterns as opposed to eight, with the disadvantage of less potentially useful information for the same computational cost.
• A splitAt function which would return two Map,s Lists or Seqs, one for the items on either side of the matching key. This would be the most versatile by far, but up to O(n) more computation and memory, so it may or may not make sense to implement this as a separate function anyway.

This is my first real contribution to F# beyond just nagging for new features, so I would appreciate any detailed feedback!

[reinux]

@dotnet-policy-service agree

[T-Gro]

I think this PR is good to attach for a new fslang-design RFC, please follow the instructions leading to a template here: https://github.com/fsharp/fslang-design#the-process

There are sections in the template to mention both the fslang-suggestion and this prototype implementation PR.

[abonie]

Ok, so here is RFC pull request https://github.com/fsharp/fslang-design/pull/734 everyone interested in this PR please share your opinions in the RFC PR

[github-actions[bot]]

:heavy_exclamation_mark: Release notes required

@reinux,

[!CAUTION] No release notes found for the changed paths (see table below).

Please make sure to add an entry with an informative description of the change as well as link to this pull request, issue and language suggestion if applicable. Release notes for this repository are based on Keep A Changelog format.

The following format is recommended for this repository:

* <Informative description>. ([PR #XXXXX](https://github.com/dotnet/fsharp/pull/XXXXX))

See examples in the files, listed in the table below or in th full documentation at https://fsharp.github.io/fsharp-compiler-docs/release-notes/About.html.

If you believe that release notes are not necessary for this PR, please add NO_RELEASE_NOTES label to the pull request.

You can open this PR in browser to add release notes: open in github.dev

Change path	Release notes path	Description
src/FSharp.Core	docs/release-notes/.FSharp.Core/10.0.100.md	No release notes found or release notes format is not correct