# Why is flatmap not using binary search to find the key?

**URL:** <https://erlangforums.com/t/why-is-flatmap-not-using-binary-search-to-find-the-key/2759>\
**Category:** Questions / Help\
**Tags:** erlang-otp\
**Created:** [July 25, 2023, 2:43am UTC](https://erlangforums.com/t/why-is-flatmap-not-using-binary-search-to-find-the-key/2759 "2023-07-25T02:43:00Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![erlangys](https://erlangforums.com/letter_avatar_proxy/v4/letter/e/c6cbf5/32.png) [@erlangys](https://erlangforums.com/u/erlangys)\
**Post date:** [July 25, 2023, 2:43am UTC](https://erlangforums.com/t/why-is-flatmap-not-using-binary-search-to-find-the-key/2759/1 "2023-07-25T02:43:00Z")

</div>

In erl\_map.c, [https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl\_map.c#L207C4-L216C3](https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl_map.c#L207C4-L216C3), it is using linear search to find the specific key. Since these keys are sorted, why not use binary search here? Similar in [https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl\_map.c#L2074-L2083](https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl_map.c#L2074-L2083)

---

<div class="post-metadata">

**Author:** ![phild](https://erlangforums.com/user_avatar/erlangforums.com/phild/32/742_2.png) [@phild](https://erlangforums.com/u/phild)\
**Post date:** [July 25, 2023, 7:45am UTC](https://erlangforums.com/t/why-is-flatmap-not-using-binary-search-to-find-the-key/2759/2 "2023-07-25T07:45:14Z")

</div>

Also, [DRY](https://github.com/inaka/erlang_guidelines#honor-dry)…

---

<div class="post-metadata">

**Author:** ![jhogberg](https://erlangforums.com/user_avatar/erlangforums.com/jhogberg/32/179_2.png) [@jhogberg](https://erlangforums.com/u/jhogberg)\
**Post date:** [July 25, 2023, 7:59am UTC](https://erlangforums.com/t/why-is-flatmap-not-using-binary-search-to-find-the-key/2759/3 "2023-07-25T07:59:59Z")

</div>

On modern hardware, binary search is nearly always slower for small collections like these (and what constitutes “small” keeps on rising). There might be a point for complex keys where the cost of comparison dominates everything else, but for immediates I’d actually be surprised if binary search was faster in the average case.

> [@phild](#):
>
> Also, [DRY](https://github.com/inaka/erlang_guidelines#honor-dry)…

A little duplication is fine. The loops are doing different things, and we wouldn’t gain anything from trying to make an abstraction that fits both uses.

---

<div class="post-metadata">

**Author:** ![erlangys](https://erlangforums.com/letter_avatar_proxy/v4/letter/e/c6cbf5/32.png) [@erlangys](https://erlangforums.com/u/erlangys)\
**Post date:** [July 25, 2023, 7:37pm UTC](https://erlangforums.com/t/why-is-flatmap-not-using-binary-search-to-find-the-key/2759/4 "2023-07-25T19:37:31Z")

</div>

Thanks for the reply. That makes sense.