I did indeed look a little bit about previous attempts at collections in Rust, but didn't find too much about ranges. What would be good keywords and place to look for, any hints?

It seems to me that you can go quite far with mutable but mutually disjoint ranges - which is more or less what slices do for vectors currently. They are also safe, because you can only split them into subslices (which borrow ownership), but not extend them (what could potentially create overlapping ranges). Moreover as long as there is any range to given container, you can't perform operations that could invalidate derived ranges (things that reallocate vector, etc.)

Range checking don't seem that bad, because in most cases it is not about trusting what a range tells you, but range trusting itself which is fine. Take you example of binary search, if range would know how to split itself in the middle, it wouldn't really have to do any bounds checking. For sorted ranges maybe operation like lower_bound or upper bound would be great primitives, or single operation that encompasses both situations:

  let (lower_range, equivalent_range, upper_range) = range.split(&value);

Of course, in general as you point out, you would have to pay a price of bounds checking for random access.

As far as I can see, this should be sufficient to implement algorithmic part. What I still find hard to do, is to modify collections based on resulting range. For example, how to write equivalent to following C++ code, that first moves consecutive duplicates to the end of array, and then erases them from container:

  std::vector<int> v { ... };
  v.erase(unique(v.begin(), v.end()),
          v.end());

I have a few ideas, which mostly boil down to following: create a description of operation to be executed, but is executed only after all ranges have returned their ownership over collection. But so far this interface have not been fully satisfactory.