> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/31.-quicksort/31.5-exercises.md).
# 31.5 Exercises
## Factual
1. Suppose we have a sorted array in Java. What is the best approach for finding a particular item in the array: binary search or linear iteration?
2. Repeat the above exercise for a sorted array stored on physical tape.
3. Given the array `[90, 50, 20, 30, 40, 10, 60, 50, 30]`, what would be the best pivot?
Problem 1
Binary search. Binary search would take $$\log N$$ time, where $$N$$ is the length of the array.
Problem 2
On a physical tape, the runtime of the algorithm will be dominated by the time to accelerate the physical piece of tape. In the worst case, binary search would involve scanning to the middle of the tape, then a quarter of the way back, then an 1/8th of the way forward, and so forth. In the worst case, we have to cover N/2 + N/4 + N/8 + ... + 1 or O(N) spaces on the tape. However, all that acceleration back and forth will result in an algorithm that is almost certainly slower in the worst case than just scanning forwards.
Problem 3
40; it is the median which will evenly partition the array.
## Procedural
1. If we have 10 items to sort, how many compares will it take to selection sort all of the items?
2. What is the depth of the quicksort recursive tree in the best and worst case? Give an exact answer, not a theta bound.
Problem 1
45 total; first we do 9 compares to find the smallest item, then 8, then 7, etc. 1 + 2 + 3 + ... 9 = 45.
Problem 2
In the worst case, we make $$N$$ recursive calls if we always choose the smallest or largest item as our pivot. Thus, the recursive tree has depth $$N$$.
In the best case, we always choose the median as our pivot. This halves the size of the array at each level, resulting in $$\log\_2 N$$ levels.
## Metacognitive
1. Assume that we always pick the leftmost item as our pivot for quicksort. Identify the three types of arrays that will cause a worst-case runtime. For partitioning, assume that we partition into two arrays: items less than or equal to the pivot, and items greater than the pivot.
Problem 1
The two types of arrays are:
1. Arrays already in sorted order. There will always be nothing to the left of the pivot, since the pivot will always be the smallest item.
2. Arrays in reverse-sorted order. This has the same problem as (1), except that the pivot will always be the largest item.
3. Arrays where all items are equal. Everything will be partitioned into the left (less than or equal to array), and nothing in the greater-than array.
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.
Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/31.-quicksort/31.5-exercises.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.