Here is a blog particularly for the Binary Search implementation. Though it is a very fundamental algorithm, it stll lays a foundation for a lot of other problems. And it is necessary to dive deep for it.

First let’s talk about the traditional implementation version of the binary search:

1 | bool search(int x[], int n, int k) { |

Observation:

- The scope of the initial boundary is [0, n - 1], which is the entire available elements set. The reason why we choose this could be explained by the update strategy for the boundary variables
`l`

and`r`

. Since they are updated as`mid - 1`

or`mid + 1`

, they could be set to any elements inside the entire scope. So we should not make the boundary exceed the valid index set. - The update strategy for the
`l`

and`r`

is reasonable when we think about a decision tree. Take left boundary`l`

for example, if the current midpoint`mid`

could not meet the predefined requirement, then all the elements on the leftside of`mid`

, while including the midpoint, should be excluded from the choice scope. And we can do this by assign`mid + 1`

to`l`

. - According to the update strategy, it is possible that we will reach the situation when
`l`

equals to`r`

. Thus, the while clause should be`l <= r`

, which includes the equality situation. - It is always helpful to consider the situation when the binary search hit the end, so that we can easily find the correct boundary and update strategy. For example, in leetcode [35], consider what will happen in the final step where l == r - 1, and there’s no element equal to target. According to the previous updating strategy,
`l`

will be set to`mid + 1`

and the binary search is finished. So the final output of the algorithm will be at the first value that is equal or bigger to the target. - The template could easily support the operations like finding equality in list and find the first element that is not satisfied the mentioned property [in this case, element in
`l`

will be the first element that is not satisfied the property]. - https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/