Find Insertion Points with bisect

Select a timestamp to watch that moment on YouTube.

1. 00:00

   Suppose a leaderboard stores scores in ascending order: ten, twenty, twenty, and forty. A new score of twenty-five is not present, but it has a clear place between the last twenty and forty. We need its insertion position, not an existing element. Python offers bisect_left for this exact question. It searches a sorted sequence and returns the first position where the target can be inserted without breaking order. We will first run a familiar list.index approach and see why it fails when the target is absent. Then we will probe positions at both ends and around duplicate values, build a function that returns a new list instead of mutating the caller's data, and verify the edge cases.

2. 00:44

   The companion lesson includes a browser console, worked examples, a checked task, common mistakes, and a quiz. Before we touch code, point to the place twenty-five should occupy. Is that an error because the value is missing, or is it the answer we actually want? Also ask which side of equal scores a new twenty should go. Both sides preserve sorted order, so we must choose a policy. This lesson chooses the left side. list.index asks where a matching element already exists. There is no twenty-five, so it raises ValueError. The scores themselves remain unchanged. Catching the exception keeps our lesson running, but it does not answer the ranking question.

3. 01:27

   A common workaround is to append the value, sort everything again, and search for it. That can be perfectly reasonable for one tiny list, but it does extra work and may mutate the original list if done carelessly. We already know scores are sorted. What we want is the boundary between values smaller than twenty-five and values greater than or equal to it. Binary search can find that boundary without scanning every element. The important precondition is sorted input. If scores were twenty, ten, forty, the boundary reasoning would fail; bisect does not silently sort for us. This is a useful debugging distinction: a failed index call does not mean the target is invalid.

4. 02:11

   It means we asked for existence when we needed placement. Let us run several searches with bisect_left and read the returned indexes as positions between elements. One of those valid positions will equal the length of the list. Five belongs at index zero, before ten. Twenty returns index one, before the two existing twenties. Twenty-five returns index three, between the second twenty and forty. Fifty returns index four, which equals the list length and means append at the end. That is not an invalid index for insertion; it would only be invalid if we tried to read scores at index four before inserting. bisect_left chooses the left edge of a run of equal values. bisect_right would return the right edge instead.

5. 02:59

   Neither changes the input. We can use the difference between right and left to count equal values, but our task needs only the left position. This search uses logarithmic comparisons in a sorted sequence, which is why the module is called bisect. Inserting into a Python list afterward can still shift many items, so the entire operation is not guaranteed logarithmic. Keep search and storage costs separate. For a small leaderboard the list approach is clear. For millions of frequently inserted records, a different data structure might make sense. Now we will create a new list, insert the score at the computed position, and preserve the original for the caller.

6. 03:43

   The returned index is one. The new list has three twenties, with the incoming one inserted at the left edge of the equal run. We cannot see which identical twenty is new just by printing the values, but the reported index makes the chosen rule observable. The original scores still contain four elements because we inserted into result, a copy. This function assumes an ascending list of comparable integer scores. It does not validate or sort input; that is part of its documented contract. If you need to accept unsorted scores, decide whether to sort a copy first and what that means for the rank you report.

7. 04:23

   Silently sorting can change the interpretation of existing positions. Notice that list.insert takes a position and a value, while bisect_left only returns the position. Those are two separate operations. You could also use insort_left, which combines them, but it mutates the supplied list. Here our explicit copy supports the promise that the caller's data remains unchanged. The browser exercise asks you to implement this exact pair of returned values. Start with the bisect result, create a copy, insert there, and test a duplicate before testing a new middle value. These assertions cover the duplicate policy, both ends of a populated list, empty input, and the untouched caller list.

8. 05:09

   They prove more than a single happy-path example. On an empty list, bisect_left returns zero and insert creates a one-element result. On a score larger than all existing values, the position equals the original length. At the left boundary, the new score becomes the first element. If a browser check fails, print both the returned index and the new list. A correct list paired with the wrong index still violates the task contract. Also check that you did not call insert on scores itself, because the task promises a new list. The key idea is not memorizing one module function name. It is asking the right question of sorted data: do I want to find an existing value, or find a place where a value belongs? list.index answers the first; bisect_left answers the second.

9. 06:00

   State the sorted-input precondition, choose a side for duplicates, and separate the fast search from the potentially linear list insertion. Once those choices are explicit, the implementation becomes small and predictable.