[48in24 Exercise] [07-02] Binary Search

Exercism 48in24
1

This issue is a discussion for contributors to collaborate in getting ready to be featured in 48in24. Please refer to this forum topic for more info.

We will be featuring Binary Search from Jul 02 onwards.

Staff jobs

These are things for Erik/Jeremy to do:

  • ☐ Check/update exercise in Problem Specifications
  • ☐ Create + schedule video

Community jobs

For each track:

  • Implement Binary Search
  • Add approaches (and an approaches introduction!) for each idiomatic or interesting/educational approach.
  • Add video walkthroughs (record yourself solving and digging deeper into the exercise).
  • Highlight up to 16 different featured exercises (coming soon)

Existing Approaches

You can use these as the basis for approaches on your own tracks. Feel free to copy/paste/reuse/rewrite/etc as you see fit! Maybe ask ChatGPT to translate to your programming language.

  • loop-with-switch (go)
  • looping (rust)
  • recursion (rust)
  • while-with-if-statements (c, cpp)

Track Statuses

You can see an overview of which tracks have implemented the exercise at the #48in24 implementation status page.

2

I’ve currently gathered the following solutions to feature:

  1. Julia: alias for built-in function
    Cheating

  2. Lua: while loop and special return value for not found
    Use a while loop that runs until left > right and return special value when value not value

  3. MIPS: loop via jumps
    Use jumps and comparison instructions to loop until left > right

  4. Crystal: recursion and nil for not found value
    Use recursion and nil for a not found value

  5. OCaml: recursion and explicit error handling via Result type
    Use recursion and the Result type for explicit error handling

  6. C#: recursion with sub-slices and offset
    Use recursion but use sub-slices of the original array whilst keeping track of the offset

  7. Raku: recursion with setup in signature
    Use recursion but setup lots in the signature

If anyone has more suggestions, do let us know!

3

You may enjoy a recursive raku solution which does all the setup in the signature by setting default values and the topic :

sub binary-search (
    :array( :@a ),
    :value( :$v ),
    :$lo                = 0,
    :$hi where $lo .. * = @a.end,
    :$mid               = ( $lo + $hi ) div 2,
    :$_                 = @a[ $mid ] cmp $v
)

so that the core comparison is all the function does :

when More { samewith :@a, :$v, :$lo, hi => $mid.pred }
when Less { samewith :@a, :$v, :$hi, lo => $mid.succ }
when Same { $mid                                     }

The built-in Order enumeration gives us human readable forms for the three-way comparison, viz Less, Same and More .

3 Likes
4

I’ll port for Wren.

3 Likes
5

Out of curiosity, the J solution is ([: I. e.), where the left argument is the value and the right argument is the set.

This is an instance of Special Combinations, a code construct that triggers non-obvious optimizations.

I find this fascinating because the code describes an algorithm that makes a trivial action, and it’s impossible to deduce its function without knowledge of these special combinations.

1 Like
6

@ErikSchierboom late to the party, but i noticed that this exercise did not get a sync in the Clojure repo. Both docs and metadata need a minor update. The toml files are in sync, but tests have not been implemented. Also, some of the community solutions are incorrect but since the tests are outdated, they are marked as correct. Even the example solution is incorrect.

I can sync everything and implement the new tests, which will catch the incorrect solutions. Let me know and i’ll open a PR.

7

That’s something we’ve been dealing with on the Emacs Lisp track. The toml files were created about three years ago, but if an exercise was implemented before that, sometimes the test suites haven’t been updated since they were first implemented. configlet sync uses what’s in the toml file so it’d be unaware of any missing tests before three years ago.

Perhaps, we can loop through the ported exercises manually and make a list of what exercises are missing tests not reported by configlet?

8

That would be great!

9

I had fun with this one in Wren. I started with the straightforward implementation, but then expanded it using wren’s Iterator protocol so I can do

var searcher = BinarySearch.new(values)
searcher.target(target)
for (index in searcher) {
  if (values[index] == target) {
    return index
  }
}
return -1

https://exercism.org/tracks/wren/exercises/binary-search/solutions/glennj

2 Likes
10

@glennj That is really neat! Unfortunately, we have already filmed the video.