4 ms·
The trick with this binary search test isn't knowing or being taught or learning the algorithm, or finding it difficult; it's making sure you find and deal with
by barrkel 17y ago
The trick with this binary search test isn't knowing or being taught or learning the algorithm, or finding it difficult; it's making sure you find and deal with every corner case, first time, without testing. For example: is an empty array handled properly? An array with duplicates? Is every item, including first and last, found correctly? What about arrays with an even number of elements vs odd, vs power of two? How about an array with over 1 billion elements (the integer overflow problem)? Are values before and after the sorted range indicated properly? If working with duplicates, do you want a found index at the start of the range, or at the end?
You get the picture.
- waterlesscloud 17y agoSo what this is really all about is this- do you mentally step through your code and consider what could go wrong at each step?
- barrkel 17y agoI would rather think in invariants - knowing what must be true at particular points in the code, at the start of loop bodies, etc. Essentially, doing a proof in one's head.