How to handle null values ​​during binary search?

Question

What is the best way to handle null during binary search on List<string> (well, it would be List<string> if I could read all the values ​​in advance)?

 int previous = 0; int direction = -1; if (itemToCompare == null) { previous = mid; for (int tries = 0; tries < 2; tries++) { mid += direction; itemToCompare = GetItem(mid); while (itemToCompare == null && insideInclusiveRange(min, max, mid)) { mid += direction; itemToCompare = GetItem(mid); } if (!insideInclusiveRange(min, max, mid)) { /* Reached an endpoint without finding anything, try the other direction. */ mid = previous; direction = -direction; } else if (itemToCompare != null) { break; } } } 

I am currently doing something like the above - if zero occurs, then linearly search in the direction until none of the non-empty or end points meet, unless success repeats in the other direction. In the actual code, I get direction from the previous comparison result, and GetItem() caches the values ​​it retrieves. Is there an easier way without doing an intermediate list of non-zero values ​​(takes too much time for my purposes, because the GetItem() function above is slow)?

I suppose I'm asking if there is a smarter way to handle null values ​​than degrading to a linear search. In all likelihood, there will be only a small percentage of zeros (1-5%), but it is possible that there will be sequences of 100 with zero.

Change The data looks something like this.

  aa aaa
 b bb bbb
 c cc
 d ddd

where each row is a separate object, and not all cells are guaranteed to be filled. The user should be able to search the entire line (so that both "bb" and "bbb" match the entire second line). The query of each object is slow enough so that the linear search does not work. For the same reason, creating a new list without zeros is not feasible.

Answer 1

If there is no reason to actually select / find the null value (not sure if this means that null is single-point, and binary search is often the most desirable by unique values), consider not allowing them to be on the list at all.

---

[ Previous answer:. After thinking about the question, I decided that null probably did not belong in the problem space - take a bit and parts if necessary.]

If null values ​​are desired, just sort the list so that the null values ​​are the first (or last) and correctly update the logic - then just make sure you don't call the method with any of the null values ​​;-)

This should have little overall impact, since sorting is already required. If the elements are changed to null - it sounds like a side effect! - then simply “compose” the list (for example, “delete” the null item). I would, however, simply not change the sorted list if there is no good reason.

Binary search is only really designed / suitable for (fully) sorted data. It makes no sense to turn it into a binary, possibly linear search.

Happy coding.