tests in `search`

[vil02]

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):

• Binary and BinaryIterative will return 4,
• Jump2 will return 4,
• Linear and Interpolation will return 2.
• Jump will 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).

[Nd1097]

Hello, would like to contribute to this. Can you assign the task?

[siriak]

I agree with for example the Interpolation function could be simplified to find some index. @vil02 do you want to implement this yourself?

[vil02]

I agree with for example the Interpolation function could be simplified to find some index. @vil02 do you want to implement this yourself?

I think @Nd1097 wanted to do it. If there will be no other volunteer you can assign me.

[tjgurwara99]

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]

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]

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]

btw, any update? @Nd1097