Half-open ranges in Python

Why this matters

Many loop bugs come from one wrong number at a boundary. A loop runs one step too many, or one step too few, and the program either prints a wrong total or crashes with an error about an index. An index is a position number in a list, and in Python positions start at 0. Programmers call these errors off-by-one errors. The name comes from the count being off by exactly one item.

A range is a group of items between two positions. Examples are the scores from week 2 to week 4, the first 10 rows of a table, or the part of a text from character 3 to character 7. When you write code for a range, you must decide two things. Is the first position included? Is the last position included? A range that includes both ends is called a closed range. A range that includes neither end is called an open range. A range that includes the start and leaves out the end is called a half-open range.

This lesson uses half-open ranges because Python uses them almost everywhere. The built-in range function makes them, a slice such as items[2:5] takes part of a list with them, and most of the standard library accepts a start and an end in the same way. Once you know the rule, you can read Python code without guessing where a range stops. The lesson does not repeat the basic for loop syntax from the earlier lessons of this module. It does not cover loops that stop when they see a value, which the sentinel loops lesson covers.

The idea in one rule

A half-open range is written [start, end). The square bracket on the left means the start is included. The round bracket on the right means the end is not included.

Python writes the same range in two ways. range(start, stop) makes the numbers of the range, and items[start:stop] takes the items. Python calls the end stop in both places, and both leave it out.

Here is a concrete case. Suppose you have five letters in a list, at positions 0 to 4: a, b, c, d, e. The range [1, 4) contains positions 1, 2 and 3. Those hold b, c and d. Position 4 holds e, and it is not in the range, because the end is left out. In Python this is letters[1:4], which gives ['b', 'c', 'd'].

Two facts follow from this rule, and they are the reason programmers like it.

The length is easy to find. The length of [start, end) is end - start. In the example, 4 - 1 is 3, and there are 3 items: b, c and d. The function len gives the same answer for a range, so len(range(1, 4)) is 3.

Neighbouring ranges fit together with no gap and no overlap. The range [0, 4) and the range [4, 5) cover all five letters. The item at position 4 belongs to the second range only. Nothing is counted twice.

Compare this with a closed range. The range [1, 3] contains positions 1, 2 and 3, and its length is 3 - 1 + 1, which is 3. The extra + 1 is easy to forget. Half-open ranges avoid it. In Python a closed range is written as a half-open one with the end moved up by one, so the closed range [1, 3] is range(1, 4).

Worked example 1: the loop that matches the range

Suppose a teacher has seven test scores, and she wants the total of the scores at positions 2, 3 and 4. Position 5 and up must not be added. We write the range as [2, 5).

The output is:

indexes 2 up to 5 give 3 items
sum = 242
length = 3
slice check = 242

The letter f before a string lets you put a variable inside braces, as in {count}. Python replaces each braced part with the value of the variable.

The loop range(start, stop) starts at start, which is 2, so the start is included. It produces 2, 3 and 4, and it stops before 5. Position 5 is never read. The last position read is 4.

The line print(f"length = {stop - start}") prints 3. This is the same number as the count the loop found. The loop ran three times, once for each of positions 2, 3 and 4. The two numbers agree because the range is half-open.

Notice that range stops before stop. This is the single most important detail in the lesson. If you write range(start, stop + 1), the loop also reads position 5, and the total becomes 321 instead of 242. The slice scores[2:5] gives the same three items, so sum(scores[2:5]) is 242 too. Programmers often use the slice when they only need the total.

Worked example 2: cutting a list into pages

A website shows 10 results, and it shows 3 results on each page. The first page holds results 0, 1 and 2. The second page holds results 3, 4 and 5. The last page holds the leftover result 9. Each page is a half-open range, and the pages must not overlap or leave gaps.

The output is:

page [0, 3) has length 3
page [3, 6) has length 3
page [6, 9) has length 3
page [9, 10) has length 1
items seen in total = 10

The table below shows the same ranges with the items they hold.

Look at the boundaries. The first page ends at 3, and the second page starts at 3. The value 3 appears as an end and as a start, but it is not an item in the first page. Position 3 belongs to the second page only. That is why the total at the bottom is 10 and not 12 or 9.

The call range(0, total, page_size) takes a third number, which is the step. The step is the amount the loop adds to the start each time. It produces 0, 3, 6 and 9, and each of these is the start of a page. Because each start is the previous start plus the page size, each page begins exactly where the one before it stopped.

The line end = min(start + page_size, total) handles the last page. min is a built-in function that returns the smaller of its arguments. Without it, the last page would start at 9 and end at 12. Positions 10 and 11 do not exist, so a page that claims them would be wrong. Taking the smaller of the two numbers keeps end at 10.

Worked example 3: the same rule in the Python standard library

Python uses half-open ranges in many of its built-in tools. Once you know this, you can predict what each one returns. The program below uses several of them.

The output is:

forge
stack
True
['b', 'c', 'd']
[20, 30]
6
4
5

A slice is a part of a list or a text, written with a start and an end inside square brackets and a colon between them. word[0:5] gives the characters from position 0 up to position 5, with 5 left out, which is forge. word[5:] leaves out the end, so it runs to the end of the text, which gives stack. word[2:2] is an empty range, because the start and end are the same. It gives an empty text, and comparing it with "" gives True.

The slice items[1:4] gives b, c and d. The slice nums[1:3] gives 20 and 30.

range(0, 4) produces 0, 1, 2 and 3. Its sum is 6 and its length is 4. Python has no separate closed version of range. To include the end 4, write range(0, 4 + 1), which has length 5. The explicit + 1 shows that the end was moved on purpose, which is the same choice as the closed range in the first section.

A range object does not store all of its numbers. It makes each number when the loop asks for it, so range(0, 1000000) uses very little memory, even though it stands for a million numbers.

Worked example 4: bookings that touch but do not clash

A meeting room is booked in blocks of hours. A booking from 9 to 10 means the room is in use during the hour that starts at 9 and ends at 10. A second booking from 10 to 11 uses the next hour. Do these two bookings clash? They should not. The room becomes free at 10, and the second booking starts at 10.

A half-open range makes this easy to check. Each booking is [start, end). Two half-open ranges overlap when each one starts before the other one ends. Written as a test, the rule is a_start < b_end and b_start < a_end. The word and means both parts must be true.

The output is:

9-10 and 10-11 overlap: False
9-10 and 9-11 overlap: True
9-10 and 11-12 overlap: False

The word def starts a function, and return sends the answer back to the caller. Python prints the answer as True or False, with a capital letter.

Take the first line. The first booking is [9, 10) and the second is [10, 11). The test checks 9 < 11, which is true, and then 10 < 10, which is false. Since the second part is false, the bookings do not overlap. The moment 10 belongs to the second booking only.

Now take the second line. The bookings [9, 10) and [9, 11) clearly share the hour from 9 to 10. The test checks 9 < 11, which is true, and 9 < 10, which is also true. Both are true, so the answer is True.

This rule is the kind of check that appears in calendars, hotel bookings and time tracking software. Once the ranges are half-open, the rule needs only one comparison in each direction and no special case for touching ends.

Common mistakes

The first mistake is writing the end as one position too far. The loop below tries to read every score, but its range ends at len(scores) + 1. The list has three items, at positions 0, 1 and 2, so len(scores) is 3. Position 3 does not exist.

The output is:

72
85
90
Traceback (most recent call last):
  File "main.py", line 3, in <module>
    print(scores[i])
          ~~~~~~^^^
IndexError: list index out of range

The path in front of main.py depends on where you saved the file, so it is shortened here. The first three lines are correct. The fourth read fails with IndexError, which is Python's name for an index outside the list. The message does not say which index failed or how long the list is, but the marks under the line point at scores[i], which is the part that failed. The fix is to end the range at len(scores). The end of a list is always left out, because range(0, len(scores)) is the range [0, len(scores)). Looping over the list directly, with for score in scores:, avoids the problem completely.

The second mistake is computing the length of a half-open range as if it were closed. The length of [start, end) is end - start, not end - start + 1. The next program counts the hours from 9 to 11 in both styles.

The output is:

closed range 9 to 11 counts 3 hours
half-open range 9 to 11 counts 2 hours

The closed version counts 9, 10 and 11 as three separate hours. To write it with range, the stop must be 12, which is the end plus one. The half-open version counts 9 and 10 as the two hours of the booking. The number 11 marks the moment the booking ends, and it is not an hour that the booking uses. If you need the closed version, say so in a comment and write the stop with + 1 on purpose.

The third mistake is a reversed range. A range where the end is smaller than the start has no items. Unlike Java's substring method, Python does not raise an error for this. It gives an empty result, and the program goes on with no items and no message.

The output is:

''
'orge'
[]

The function repr shows a value with its quotes, so an empty text appears as ''. The slice word[2:1] is reversed, and it gives nothing. The slice word[1:99] asks for an end past the end of the text, and Python stops at the last character, which gives orge. Neither case raises an error, so check the order of the numbers, start first and end second, before you look anywhere else.

The fourth mistake is going past the end of a list with a single position. A single index such as items[9] raises an error when the position does not exist. A slice does not. The next program shows both, and it catches the error with try and except.

The output is:

index error: list index out of range
['b', 'c', 'd', 'e']
['b', 'c']

A try block runs code that might fail. If the named kind of error happens inside it, the except block runs instead, and the program carries on. Here IndexError is the name of the error for a single position that does not exist. The slice items[1:9] does not fail. It returns the items that exist, from position 1 up to the end of the list, which are b, c, d and e. A slice quietly stops at the end of the list, so a wrong end in a slice gives fewer items and no message.

The fifth mistake is double counting at a shared boundary. Two ranges that share a boundary value are fine when the shared value is an end in one range and a start in the other. They are wrong when both ranges include it. For example, range(0, 5) and range(5, 9) cover positions 0 to 8 exactly once. If you write the first one as [0, 5], position 5 appears in both ranges, and the total is counted twice.

The output is:

9
[5]
10

The first line shows that the two half-open ranges hold 9 items in total, which is the number of positions from 0 to 8. A set is a collection with no repeated values, and the & symbol between two sets gives the values they share. The second line shows that position 5 is in both ranges once the first one is written with 6 as its stop. The last line shows the total going up from 9 to 10.

Practice

Exercise 1. The list temps = [18, 21, 19, 25, 23, 22, 20] holds seven daily temperatures. Write a loop that adds up the temperatures at positions from 1 up to but not including 4, and print the total. Use the half-open range [1, 4).

Show the answer

The positions are 1, 2 and 3, which hold 21, 19 and 25. Their total is 65. The loop uses range(1, 4), which starts at 1 and stops before 4.

total = 0
for i in range(1, 4):
    total += temps[i]
print(total)

The output is 65. The same total comes from the slice sum(temps[1:4]).

Exercise 2. Give the length of each range: [4, 11), [7, 7) and [20, 26).

Show the answer

The lengths are 11 - 4, which is 7, then 7 - 7, which is 0, then 26 - 20, which is 6. In Python the same answers come from len(range(4, 11)), len(range(7, 7)) and len(range(20, 26)), which print 7, 0 and 6. An empty range has length 0 and no items.

Exercise 3. A cinema has 100 seats, numbered 0 to 99. It sells them in four blocks of 25 seats. Write the four half-open ranges that cover all 100 seats, with no seat in two blocks.

Show the answer

The ranges are [0, 25), [25, 50), [50, 75) and [75, 100). In Python, the loop for start in range(0, 100, 25): print(range(start, start + 25)) prints them as these four lines.

range(0, 25)
range(25, 50)
range(50, 75)
range(75, 100)

Each end is the next start, so no seat is missed and no seat is counted twice. The last end is 100, which is the number of seats, so the last seat is 99.

Exercise 4. Using the overlaps function from worked example 4, decide whether these two bookings clash: 13 to 14, and 14 to 15. Then decide whether 13 to 15 and 14 to 15 clash.

Show the answer

The first pair does not clash. The test checks 13 < 15, which is true, and 14 < 14, which is false, so overlaps returns False. The second pair does clash. The test checks 13 < 15 and 14 < 15, which are both true, so overlaps returns True. The hour from 14 to 15 is shared.

Summary

• A half-open range [start, end) includes the start and leaves out the end.
• The length of the range is end - start, and range(start, end) gives exactly those numbers.
• Two ranges that share a boundary value cover all items once when one ends where the other starts.
• Python's range and slices such as items[1:4] use half-open ranges.
• Use stop + 1 in range only when you mean to include the end, and say so in a comment.