equinor / equinor/esv-intersection

`BinarySearch` wrongly select the center of the array

Open
#1,036 1 comment 0 reactions 0 assignees View on GitHub
🐛 bug
Dominant language
TypeScript
Stars
17
Forks
8
Avg merge
1d 11h
Merged PRs (30d)
17

Description

## Description

The `BinarySearch` seems to wrongly select the center of the array, see [binary-search.ts](https://github.com/equinor/esv-intersection/blob/fbd5030f2b34406ea77a76013c3000d24a9726fb/src/utils/binary-search.ts#L10)

Esv-intersection uses:

`let i = Math.floor(il + ih / 2);`
and
`i = Math.floor(il + ih / 2);`

when it should be
`let i = Math.floor((il + ih) / 2);`
and
`i = Math.floor((il + ih) / 2));`

This issue has been introduced in https://github.com/equinor/esv-intersection/pull/441 where we can see that the center of the array was properly selected before.

Image

See more info on BinarySearch in for instance https://www.w3schools.com/dsa/dsa_algo_binarysearch.php

### Is the selected algorithm correct?

❗ **The binary search in itself is also peculiar**, it is not the standard one, and seems to allow for approximation (especially with the condition `v <= searchValue && v1 >= searchValue`)
=> look into if the implementation is correct and should be kept or if the binary implementation should be standard & fixed

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with src/utils/binary-search.ts, especially the two midpoint calculations linked in the issue. Compare the current approximation-oriented conditions with the standard binary-search behavior and verify how the incorrect midpoint affects results. Done means the midpoint selection and overall search behavior are confirmed correct, with the implementation fixed or its intended approximation behavior clarified.

Written by the indexing model from the issue text.

Assessment

Tech stack
typescript
Domain
tooling
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.