Basic

Searching a sorted row

A sorted row can be searched faster than a shuffled one. If you know the order, you can throw away half the row at a glance, which is the start of binary search.

What you will see

True

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Search a sorted row with bisect.

Find where 4 belongs.

import bisect nums = [1, 3, 5, 7] print(bisect.bisect_left(nums, 4))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Insert keeping order.

import bisect nums = [1, 3, 5] bisect.insort(nums, 4) print(nums)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[1, 3, 4, 5]

Count how many equal 2.

import bisect nums = [1, 2, 2, 3] lo = bisect.bisect_left(nums, 2) hi = bisect.bisect_right(nums, 2) print(hi - lo)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Check membership in a sorted row.

nums = sorted([8, 2, 6, 4]) print(6 in nums)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

True

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

A sorted row can be searched by halving, and bisect finds where a value belongs or how many match.

1 row is sorted

↓

2 middle tells which half

↓

3 bisect finds the spot

↓

4 sort once, search many

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

import bisect sets nothing on screen

nums = [1, 3, 5, 7] sets nothing on screen

print(bisect.bisect_left(nums, 4)) 2

Why this works

Sort to search often

Sorting costs work once. If you then ask many membership or range questions, that one sort makes each answer fast.

bisect is binary search

The standard library bisect works on sorted rows. It is the ready-made version of the halving idea.

Examples

Look in a phone book

nums = [1, 3, 5, 7, 9]
print(5 in nums)

A sorted row lets you stop early. Once a value is past where you are, the rest cannot hold it.

Sorted helps find

nums = sorted([9, 1, 5])
print(nums)

Sorting first costs work, but then many searches are cheap. Sort once, search many times.

Half at a glance

nums = [1, 3, 5, 7, 9]
mid = len(nums) // 2
print(nums[mid])

The middle value tells which half to keep. That halving is binary search, covered next.

Unsorted must scan

nums = [4, 1, 3]
found = False
for x in nums:
    if x == 3:
        found = True
print(found)

With no order you must check every item. Order is what lets a search skip ahead.

Find the first place

nums = [1, 3, 5, 7]
import bisect
print(bisect.bisect_left(nums, 4))

bisect finds where a value belongs in a sorted row. That index is the insertion point.

Insert keeping order

import bisect
nums = [1, 3, 5]
bisect.insort(nums, 4)
print(nums)

insort puts a new value in the right spot. The row stays sorted without a full re-sort.

Range of a value

import bisect
nums = [1, 2, 2, 3]
lo = bisect.bisect_left(nums, 2)
hi = bisect.bisect_right(nums, 2)
print(hi - lo)

Left and right bounds give how many items equal a value. That count is a range in one row.

Sorted once, many asks

nums = sorted([8, 2, 6, 4])
print(6 in nums)

One sort pays for many questions. If you ask often, sort first.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Selection sort

Previous Lesson

Selection sort

Next Lesson

Stability and ties

Stability and ties →