Hello everyone,
When writing algorithms operating on sequences, we need to be precise with how we deal with bounds.
For instance, in C, we usually write loops such as:
for (i = 0; i < n; i++) { ... } // exclusive bound
But in other language, we'd write.
for i = 0 to n - 1 // inclusive bound
Similarly, let say we write a binary search function binary_search(arr, i, j), we need to to decide whether j is included or not.
How do you decide which version to use? Do you try to be consistent or do you decide depending on the problem?
I don't find a big difference so I usually do whatever comes first, although exclusive end can be nice if you split the range: if you binary search in range [i, j), then splitting on the middle gets [i, mid), [mid, j). With inclusive end you just need to deal with +1 -1, which is not a big deal anyway.
It's personal preference I guess. Since most range query problems use 1-based indexing and inclusive bound I usually use inclusive bounds. But usually exclusive bound allows better looking code. Like size is r - l not r - l + 1, we iterate till < r not < = r.