Repository navigation
tests in search #575
Description
The search functions cannot be treated uniformly in tests. The issue arises when the input array contains duplicated entries.
Consider the example when we want to fund the index of 4 in the array [1, 2, 4, 4, 4, 6, 7, 8, 9, 10] (note that the array is sorted):
BinaryandBinaryIterativewill return 4,Jump2will return 4,LinearandInterpolationwill return 2.Jumpwill return 2.
To summarize the functions like Linear or Interpolation return the smallest index of the searched element (if it exists in the array). While other functions like Binary or Jump2 return some index.
I think the above shows a need to change tests or/and the implementations of the search package (for example the Interpolation function could be simplified to find some index).
Activity
Nd1097 commentedon Oct 19, 2022
Hello, would like to contribute to this. Can you assign the task?
siriak commentedon Oct 24, 2022
I agree with
for example the Interpolation function could be simplified to find some index. @vil02 do you want to implement this yourself?vil02 commentedon Oct 30, 2022
I think @Nd1097 wanted to do it. If there will be no other volunteer you can assign me.
tjgurwara99 commentedon Nov 8, 2022
For the test cases that are present in the tests, they are correct. I argue that those specific test cases should be added on case by case basis rather than uniformly adding them in tests separately for each test.
KreanXie commentedon Jun 30, 2023
I don`t think the Binary func is useful when the array has repeated elements, maybe we can just refer to the sort.Search func in the standard library, which has a more clear and strict definition.
aminoxix commentedon Jun 8, 2025
if the binary func intends to find the smallest index, you might be referring to lower & upper bound algorithm.
ref.: https://peng.fyi/post/binary-search-in-go-sdk
we can segregate the concepts to attend this issue.
also, agreed with @tjgurwara99
aminoxix commentedon Jun 8, 2025
btw, any update? @Nd1097