Блог пользователя Tomzik

Автор Tomzik, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.