Search Space

Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space.

https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-clean-java-code

The key point for any binary search is to figure out the "Search Space". For me, I think there are two kind of "Search Space" -- index and range (the range from the smallest number to the biggest number). Most usually, when the array is sorted in one direction, we can use index as "search space", when the array is unsorted and we are going to find a specific number, we can use "range".

search index ===> LC153
search range ===> LC 287, Copy Books, LC 378
- Usually, search by range needs a helper function to determine whether save left half or right half

九章

Level 1: OOXX

the last position of O?

check right element first after the loop

the first position of X?

check left element first after the loop

Level 2: Half half

according to a condition, save half of the elements

Level 3: Binary Search on Result

do Binary Search on the range of result
think twice about what's the range! where is the start and where is the end?

Template

I would rather leave the range a little bit bigger, than accidentally miss the result.

while (start + 1 < end) {
    int mid = start + (end - l) / 2;

    if (xx == oo) {
        start = mid; / end = mid;
    } else if (xx < oo) {
        end = mid;
    } else if (xx > oo) {
        start == mid
    }
}

//check start element first, if finding the first position of sth
//check end element first, if finding the last position of sth

return start or end

Binary Search and its variation

http://fihopzz.blogspot.com/2013/07/enter-post-title-here-binary-search-and.html

Binary Search