Skip to content

unclear behavior of binary search on unsorted structures #106746

Closed
@max397574

Description

@max397574

Location

Local docs from rustup under /std/primitive.slice.html#method.binary_search
also for VecDeque and the other binary search functions (search_by)

Summary

There is written https://doc.rust-lang.org/nightly/std/primitive.slice.html#method.binary_search

Binary searches this slice for a given element. This behaves similarly to contains if this slice is sorted.

To me this first sounded like the binary search would work on all the slices and if it would be sorted sth would be different. Some people told me that it won't work if the slice isn't sorted and it will just output garbage.

If this really is the case it should be written that it only works for sorted slices (and VecDeques).
In any case the different behaviors when sorted and unsorted should be clarified
(e.g. if linear search is done on unsorted slice)

Activity

added
A-docsArea: Documentation for any part of the project, including the compiler, standard library, and tools
on Jan 11, 2023
added
E-easyCall for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.
on Jan 13, 2023
jofas

jofas commented on Jan 13, 2023

@jofas
Contributor

I'd be happy to add warnings and examples to the documentation of the binary_search_[by] methods of slice and VecDeque. @scottmcm can I claim this issue?

workingjubilee

workingjubilee commented on Jan 16, 2023

@workingjubilee
Member

@jofas Go for it. In the future you can @ rustbot claim.

jofas

jofas commented on Jan 16, 2023

@jofas
Contributor

thanks @workingjubilee, will do next time 🙂

added a commit that references this issue on Mar 30, 2023

Rollup merge of rust-lang#106985 - jofas:106746-fix, r=ChrisDenton

d6f2740
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

A-docsArea: Documentation for any part of the project, including the compiler, standard library, and toolsE-easyCall for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

    Participants

    @scottmcm@jofas@workingjubilee@max397574

    Issue actions

      unclear behavior of binary search on unsorted structures · Issue #106746 · rust-lang/rust