Tomzik's blog

Inclusive/exclusive bounds
By Tomzik, history, 7 years ago, In English

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?

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply