The pattern and binary search in Python

Why it matters

Divide and conquer is the idea behind some of the fastest sorting methods, many fast search tricks, and a large share of the problems asked in technical interviews. Binary search is the simplest form of it. You will write it in this lesson, test it, and then learn three variations that come up again and again. Python's standard library also has a ready-made version, and you will see how to use it.

Most beginners first meet searching as a loop that checks every item. That works, but it gets slow when the list is large. Divide and conquer gives you a way to avoid checking most of the items at all. This lesson builds that idea from the ground up, so you can see why it works and not just memorize the code.

You need to know what a list is and how a for loop and an if statement work in Python. If those feel shaky, go back to the arrays lesson in this track first.

The idea in plain words

A divide and conquer method solves a big problem in three steps.

1. Divide: split the problem into smaller problems of the same kind.
2. Conquer: solve each smaller problem. Usually you do this by calling the same function on it, which is called recursion.
3. Combine: join the smaller answers into the answer to the big problem.

Recursion means a function calls itself on a smaller input. You will see it in the last section of this lesson. For now, hold onto the three steps.

Here is an everyday picture. Suppose you want to find the word "lantern" in a printed dictionary of 1,000 pages. You do not start on page 1 and turn pages one by one. You open the book near the middle. Say you land on page 500, and the words there come before "lantern" alphabetically. You know "lantern" cannot be on pages 1 to 500, so you throw that half away. You open the remaining half near its middle, and repeat. Each look at a page throws away half of what is left.

That is binary search. Each step cuts the search area in half. The word "binary" means two. Each step has two possible outcomes: the target is in the left half or the right half. You keep only the half that can still hold the target.

Notice what made the trick work. You could tell which half to throw away by looking at one item in the middle. That only works because the dictionary is in order. Without that order, a word on page 500 would tell you nothing about the words on pages 1 to 499.

The one rule: the data must be sorted

Binary search needs a sorted list. Sorted means the values go in order, usually smallest to largest. If the list is not sorted, throwing away half is not safe, and the search can miss an item that is there.

Here is a small case that fails. Look for 2 in the unsorted list [9, 1, 8, 2].

• The search area is all four items, indexes 0 to 3. The middle index is 1, which holds 1.
• 1 is less than 2, so the search throws away the left half and keeps indexes 2 and 3.
• The middle of that area is index 2, which holds 8. That is greater than 2, so the search throws away the right half.
• Nothing is left, so the search says 2 is not there.

But 2 is at index 3. The function did not crash. It just gave a wrong answer, and nothing in the output tells you so. That is the most dangerous kind of bug, so check that your data is sorted before you use this method.

The precise version: low, high and mid

To write the function, you track the search area with two numbers. Here are the names used throughout this lesson.

• low: the index of the first item still in the search area.
• high: the index of the last item still in the search area.
• mid: the index halfway between them, which is the item you check.

Start with low = 0 and high = len(a) - 1. Python lists start at index 0 too. len(a) is the number of items, so the last index is one less. Then repeat these steps while low <= high.

1. Compute mid. The // symbol means whole-number division that drops any fraction, so 7 // 2 is 3.
2. If a[mid] equals the target, you are done. Return mid.
3. If a[mid] is less than the target, the target must be to the right of mid. Set low = mid + 1. Adding one skips the item you just checked.
4. Otherwise the target must be to the left of mid. Set high = mid - 1.

If the loop ends without a match, the target is not in the list, so return -1. A value of -1 is a common way to report "not found," because no valid index is negative.

Notice the "+ 1" and "- 1" in steps 3 and 4. They are not decoration. Once you have checked mid, you know it is not the answer, so you remove it from the search area too. If you wrote low = mid instead, the area might never shrink, and the loop could run forever. You will see this bug in the common mistakes section.

The loop condition low <= high also matters. When low equals high, one item is still in the search area, and you must still check it. If you wrote low < high, you would skip that last item. You will see that bug in the debugging section too.

Worked example 1: searching for 23

Here is the complete function with a test. The list holds seven sorted numbers. The program searches for five targets and prints the index of each, or -1.

The : list[int] and -> int parts are type hints. They tell a reader what kind of values the function expects. Python does not check them while the program runs, so they are notes for people and for editor tools.

The line if __name__ == "__main__": means "run the code below only when this file is started directly." When another file imports this one, the test code does not run. You will use this line in every program in the course.

This program needs no input. Click Run and you should see:

search 23 -> 5
search 7 -> -1
search 2 -> 0
search 38 -> 6
search 40 -> -1

Now trace the first search by hand, because the trace is the best way to understand the function. The list is [2, 5, 8, 12, 16, 23, 38]. The target is 23.

• Step 1: low is 0 and high is 6. The middle is 0 + (6 - 0) // 2, which is 3. a[3] is 12. That is less than 23, so low becomes 4. The area is now indexes 4 to 6.
• Step 2: low is 4 and high is 6. The middle is 4 + (6 - 4) // 2, which is 5. a[5] is 23, which matches. The function returns 5.

Two checks found 23. A plain scan from the start would need six checks to reach index 5. With a bigger list, the gap grows fast.

Now step through the same kind of search yourself. The visualizer below runs binary search on a sorted list and shows low, high and mid as they move.

After the animation, watch three things. First, the search area always shrinks, and it shrinks by about half at each step. Second, mid always sits in the middle of the area. Third, when the target is found, the loop stops at once. Try a target that is not in the list and watch the area shrink to nothing before the loop ends.

Worked example 2: a target that is not there

Now search for 7, which is not in the list. Trace every step, because a missing target is where most mistakes hide.

• Step 1: low 0, high 6, mid 3. a[3] is 12. Is 12 less than 7? No, it is bigger, so high becomes 2.
• Step 2: low 0, high 2, mid 1. a[1] is 5. Is 5 less than 7? Yes, so low becomes 2.
• Step 3: low 2, high 2, mid 2. a[2] is 8. Is 8 less than 7? No, so high becomes 1.
• Now low is 2 and high is 1. low is past high, so the loop stops. The function returns -1.

Three checks were enough to prove that 7 is missing. The last step is important. The loop did not end because it found something. It ended because the search area became empty. An empty area is a valid state, and the loop handles it because the condition is low <= high, not low < high.

Worked example 3: a program that reads its input

Test programs often take their data from the person running them, not from code inside the file. This program reads the size of the list, the numbers, and the target from standard input. Standard input is the text a program receives while it runs. It is usually what you type in a terminal.

The line sys.stdin.read() returns all the text that arrives. split() breaks that text on any spaces or line breaks, so it does not matter whether your numbers sit on one line or several. This is how Python reads input in short programs.

import sys
 
 
def binary_search(a: list[int], target: int) -> int:
    low = 0
    high = len(a) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
 
 
def main() -> None:
    # read() returns all the text that was typed or piped in.
    # split() breaks it on any spaces or line breaks.
    data = sys.stdin.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1 : 1 + n]]
    target = int(data[1 + n])
    index = binary_search(a, target)
    if index >= 0:
        print(f"found at index {index}")
    else:
        print("not found")
 
 
if __name__ == "__main__":
    main()

Save the file as search_input.py. Then run this command in a terminal:

printf '7\n2 5 8 12 16 23 38\n23\n' | python3 search_input.py

The printf command writes the three lines into the program's input, and the vertical bar sends them to Python. On Windows, where printf may not exist, run python search_input.py, type the three lines yourself, and press Ctrl+Z and then Enter to end the input. The first line, 7, is the number of items. The second line holds the seven numbers. The third line is the target. The program prints:

found at index 5

Now change the last number in the command to 7. The output changes to not found.

Why the middle is written this way

You may wonder why the code does not write mid = (low + high) // 2. That form is shorter and looks right. In Python it is safe, and the reason is different from the one in most other languages.

In many languages, an integer has a fixed size. If the sum of two large numbers is bigger than that size, the value wraps around and becomes a wrong number, sometimes a negative one. A reader who knows Java or C will recognize this trap. Python integers have no fixed size. They grow to fit whatever value you compute, so the sum is always exact.

The program below shows both forms on large numbers, and it shows how big a Python integer can get.

The output is:

(low + high) // 2 = 1750000000
low + (high - low) // 2 = 1750000000
2 ** 100 = 1267650600228229401496703205376
type of low: int

Both forms give the same answer in Python. The underscores in 1_500_000_000 are only a way to make big numbers easier to read. The 2 ** 100 value is far larger than any fixed-size integer, and Python handles it without a problem.

Keep the form low + (high - low) // 2 anyway. Your code may later move to a language with fixed-size integers, and interviewers often ask about this detail. It costs nothing in Python.

What it costs: why the number of steps is small

Each step cuts the search area in half. Start with n items. After one step about n / 2 remain, after two about n / 4, and so on. The search stops when one item or none is left. The number of halvings needed to get from n down to 1 is about log base 2 of n. The mathematical name for this cost is O(log n), read "order log n." It means the number of steps grows very slowly as the list grows.

Here is a program that counts the loop steps for a 1,000-item list. The list holds the even numbers from 0 to 1,998. The function returns the index and the step count as a pair, which Python calls a tuple.

The output is:

target 0: index 0, loop steps 9
target 1998: index 999, loop steps 10
target 1000: index 500, loop steps 9
target 1001: index -1, loop steps 10

The line a = [2 * i for i in range(1000)] is a list comprehension. It builds a list by running an expression for each value in a range. It is shorter than writing a loop that appends each value.

Even the worst case took 10 steps for 1,000 items. A plain loop that checks every item would take up to 1,000 steps. On a list of one million items, binary search needs at most about 20 steps, while a plain loop may need a million. Each doubling of the list adds only one more step. That is the power of splitting in half again and again.

Study the table to see how small the numbers stay.

What happens inside: memory and the loop

It helps to picture what the computer keeps in memory during the search. A Python list stores one reference per slot. A reference is a pointer that says where a value lives in memory. The slots sit one after another, so a[mid] jumps straight to one slot. That jump takes the same time no matter how long the list is. This is called constant-time access, and it is why binary search can check an item in one step.

During the search, the function keeps only three variables: low, high and mid. Each holds one small whole number, so the extra memory is fixed and small. The loop version uses O(1) extra space. The word "space" here means memory beyond the list itself.

The loop changes only those three numbers. Everything else stays put. That is why the loop is easy to trace on paper. Write low, high and mid on a sheet and cross out the half you throw away each time.

Variation 1: finding the first position with duplicates

Real data often has repeated values. Suppose you have the sorted list [1, 2, 2, 2, 5, 7] and you want the first position where 2 appears, or the position where 2 would go if it were missing. The standard binary search returns whichever 2 it happens to land on first, which might be index 2 or 3. This variation finds the first one.

The method is called a lower bound. It returns the first index whose value is not less than the target. If the target is missing, it returns the spot where the target would be inserted. Look at this version. It uses a half-open range, meaning high starts one past the last index and the loop runs while low is less than high.

The file also shows the lower bound from Python's standard library, the bisect module, so you can compare the two.

The output is:

value 0 first position 0 present False
value 2 first position 1 present True
value 3 first position 4 present False
value 7 first position 5 present True
value 8 first position 6 present False
bisect_left: [0, 1, 4, 5, 6]
bisect_right for 2: 4
bisect_left 23 in b: 5
bisect_left 7 in b: 2
bisect_left 40 in b: 7
bisect_left 10 in b: 3

Look closely at the line for 8. The answer is 6, which is one past the last index. That is correct: 8 would go after everything, at the very end. This is why the range is half-open. The function never has to return -1, and the caller checks present separately.

The branch is different here. When a[mid] is less than the target, the function moves low to mid + 1. When a[mid] is equal or bigger, it keeps mid as a possible answer by setting high = mid. It does not return early. It keeps shrinking until low and high meet, and the meeting point is the answer. For 2 in [1, 2, 2, 2, 5, 7], the loop ends at index 1, the first 2.

The bisect module does the same job in one call. bisect_left returns the lower bound, the first index where the target fits. bisect_right returns the position after the last copy of the target. Each one returns an insertion point, not -1, so you check for a match yourself, as the line present does. For 7 in the list b, the answer 2 is where 7 would go to keep the list sorted, between 5 and 8.

Use this pattern whenever a question asks "where does it start?" or "how many items are less than x?" Counting is easy after you have the lower bound. The number of items less than x is simply the lower bound of x, because the first index that is not less than x equals the count of smaller items.

Variation 2: binary search on the answer

So far you have searched for an item in a list. The same halving idea works when you search for a number that answers a question. Suppose you need the whole-number square root of 50. The true square root is about 7.07, so the answer is 7. You do not have a list of square roots to search. Instead, you guess a number and check whether it is too big or too small.

The guess-and-check test is: does mid * mid fit under n? If it does, mid is a valid answer, so try a bigger one. If not, mid is too big, so try a smaller one. Once the test flips from true to false, the search has found the boundary. This works because squares only grow as the guess grows.

The program below reads a number from standard input and prints its whole-number square root. The math module already has this function as math.isqrt, and the program checks its own answer against it.

import math
import sys
 
 
def floor_sqrt(n: int) -> int:
    low = 0
    high = n
    answer = 0
    while low <= high:
        mid = low + (high - low) // 2
        if mid * mid <= n:
            answer = mid
            low = mid + 1
        else:
            high = mid - 1
    return answer
 
 
if __name__ == "__main__":
    n = int(sys.stdin.read())
    print(f"floor of square root of {n} is {floor_sqrt(n)}")
    print("math.isqrt agrees:", floor_sqrt(n) == math.isqrt(n))

Save it as isqrt_search.py and run this command:

printf '50\n' | python3 isqrt_search.py

The output is:

floor of square root of 50 is 7
math.isqrt agrees: True

Notice the difference from the first search. When mid * mid is small enough, the function saves mid in answer and moves low up, so it keeps looking for a bigger valid answer. The variable answer is the best valid guess so far. The loop ends when the search area is empty, and answer holds the largest valid value. This pattern, "save the best valid guess and keep looking," appears in many interview problems.

In Java or C, the square of a big number can overflow a fixed-size integer, and programmers switch to a larger type. In Python you do not need that step. The multiplication always gives the exact answer.

Variation 3: the recursive version

Divide and conquer is naturally recursive. Each step solves a smaller version of the same problem, which means calling the function on a smaller range. Here is binary search written that way. The function takes the range as two extra parameters, and it calls itself on the half that can still hold the target.

The file also shows what happens when recursion goes too deep, because Python limits how many calls can be active at once.

The output is:

0
7
-1
6
recursion limit: 1000
count_down(500) = 0
RecursionError: maximum recursion depth exceeded

The first if is the base case: the simplest version of the problem, which needs no further calls. When the range is empty, the answer is -1. The other two lines each make one call on a smaller range, and they do no more work than that. Recursion is a good fit for this problem because the shape of the solution matches the shape of the problem.

The function count_down is there only to show the limit. It calls itself 500 times and returns, which is fine. Asked to go 5,000 calls deep, it raises a RecursionError. The limit is 1000 by default, as the output shows. Binary search never gets near that limit, because a list of a billion items needs only about 30 levels. Use the loop version when you are not sure how deep the calls will go.

What happens inside: the call stack

Every call to a function gets its own small block of memory called a stack frame. The frame holds that call's parameters and local variables. The frames stack up in order, like plates. The newest call sits on top, and when it returns, its frame is removed and the call below it continues.

For the search for 3 in the list above, the stack grows like this: the first frame has range 0 to 7, the second has range 0 to 2, and the third has range 0 to 0. Then the search finds 3 at index 0, and the frames return one by one. Each return passes the answer back to the frame below.

The depth of the stack matches the number of halvings. For 1,000 items that is about 10 frames, which is nothing. For a list of one million items it is about 20 frames. This is why the recursive version also uses O(log n) space for the stack. The loop version does not need that stack, so it uses O(1) space. Interviewers often ask you to explain this difference.

Edge cases you must test

Good code handles the edges, and interviewers check them first. Test each of these before you trust a search function.

• Empty list. len(a) - 1 is -1, so high starts below low. The loop never runs, and the function returns -1. bisect.bisect_left([], 5) returns 0, which is the insertion point in an empty list, so check for a match before you trust that result.
• One item. The loop runs once. Check both the match and the miss.
• Target smaller than every item or bigger than every item. The search area shrinks to nothing and the function returns -1.
• Target at the first or last index. These are the cases where an off-by-one error shows up. Test both.
• Duplicates. The plain search may return any copy. Use the lower bound when you need a specific one.

Common mistakes and the messages they produce

Some mistakes produce an error message that tells you exactly what went wrong. Others produce wrong answers in silence. Learn to recognize both.

Mistake 1: high starts at len(a). This is the most common off-by-one error. If high is 7 for a 7-item list, mid can also be 7, and a[7] does not exist. Python stops the program and prints a traceback, which is the list of calls that led to the error. Here is the buggy function run on a 7-item list, with a target bigger than every item.

def buggy_search(a: list[int], target: int) -> int:
    low = 0
    high = len(a)  # bug: should be len(a) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
 
 
print(buggy_search([2, 5, 8, 12, 16, 23, 38], 100))

The output is below. The directory part of the file path depends on where you save the file, so it is shortened here.

Traceback (most recent call last):
  File "/path/to/buggy_search.py", line 15, in <module>
    print(buggy_search([2, 5, 8, 12, 16, 23, 38], 100))
          ~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/path/to/buggy_search.py", line 6, in buggy_search
    if a[mid] == target:
       ~^^^^^
IndexError: list index out of range

Read the traceback from the bottom. The last line names the kind of error, which is IndexError, and the message, which is list index out of range. Just above it, the line that failed is shown with a caret pointing at a[mid]. The traceback also gives the line number of the failing code, which is line 6 in this file. The fix is high = len(a) - 1.

Mistake 2: a negative index does not always raise an error. Python allows negative indexes. a[-1] means the last item, a[-2] means the second to last, and so on. A bug that makes high equal -1 can therefore read the wrong item without any error. The program below shows both cases.

The output is:

a[-1] = 8
IndexError: list index out of range

The first line did not fail, because -1 is a valid index in Python. The second line failed because the list is empty. When you write a search, check that high never becomes negative while the list is non-empty.

Mistake 3: low = mid or high = mid in the wrong place. If the update does not move past mid, the search area can stop shrinking. When low and high are next to each other, mid equals low, and low = mid changes nothing. The loop repeats forever. Your program then runs until you stop it. Use mid + 1 and mid - 1 for the two plain updates, and use high = mid in the lower bound variation, where mid stays a candidate.

Mistake 4: running binary search on unsorted data. No error appears. The function returns a wrong index or -1 for a value that is in the list. The program below runs the function on the unsorted list from the start of this lesson, and it compares the result with list.index, which checks every item.

The output is:

unsorted [9, 1, 8, 2], target 2 -> -1
2 is at index 3

When an answer looks wrong, check whether the input is sorted before you check the code.

Mistake 5: a loop condition that skips the last item. Using while low < high in the plain version misses the case where one item is left. The search can then return -1 for an item that is in the list, such as the last one. You will see this bug in the debugging walkthrough.

Debugging walkthrough: why does the last item go missing?

Suppose a teammate wrote the loop with low < high, and then reports that searching for 38 returns -1 even though 38 is the last item in the list. Here is how you find the bug without guessing.

First, reproduce the problem with a small test. The bug only shows at the end of the list, so the test must target the last item. Copy the function and keep the print line at the top of the loop. That line shows the state at each pass. The printed lines tell the story.

The output is:

low=0 high=6 mid=3
low=4 high=6 mid=5
returned -1

Read the trace. After the second pass, low is 4 and high is 6 before the update, and mid is 5. The value at 5 is 23, which is less than 38, so low becomes 6. Now low and high are both 6, so the loop condition low < high is false. The loop stops, and it never checks a[6], which holds 38. The bug is clear now: the condition should be low <= high, so the last item still gets checked.

This is the method you should use every time. Form a guess about the bug, then make the program show you the state at each step. Do not change code at random and hope. Print low, high and mid on each pass, and compare the trace with what you expected. For a function this small, the trace takes less than a minute, and it saves you from many wrong fixes.

Also check the boundary cases. Test the first item, the last item and a missing item after each change. Most search bugs are at a boundary, and the common mistakes list above is a checklist of them.

Interview questions and real-world uses

Interviewers ask about binary search in a few common ways.

• "What is the time complexity?" Answer O(log n) time and O(1) space for the loop version, and explain why each step halves the range.
• "Why do you use low + (high - low) // 2?" Explain that in fixed-size integer languages the simple sum can overflow, and that Python avoids this by growing its integers. Showing that you know the trap is worth more than a memorized formula.
• "Find the first or last occurrence of a value." Use the lower bound, or its mirror, the upper bound, which keeps going right when it finds a match. In Python, bisect_left and bisect_right do this.
• "How many items are less than x?" Use the lower bound. The answer is the lower bound index, because it equals the count of smaller items.
• "Search when you do not have a list." Explain binary search on the answer: test a guess with a yes or no check that flips once.

Python's standard library has no binary_search function that returns -1. It has the bisect module instead. bisect_left returns the insertion point, and you check a[i] == target yourself. Knowing this difference is useful when you read code from other languages. For example, Java's Arrays.binarySearch returns a negative number that encodes the insertion point, and Python code does not do that.

Binary search is everywhere in real software. A database table can have an index, which is a sorted copy of one column with a pointer back to each row. When you ask for every customer with an ID between two values, the database uses a search like the ones in this lesson to jump to the first matching entry and then reads forward. Without the index, it would read every row. Spell checkers and autocomplete boxes also keep sorted lists of words and search them the same way. In each case the speed comes from the same fact: a sorted list can be cut in half at each step.

Explaining binary search out loud

In an interview, the code matters less than the explanation. Interviewers want to hear that you understand why the function works, so practise saying it in four short sentences.

First, say what you are looking for and what you know about the input. For example: "The list is sorted, and I want the index of the target or -1."

Second, say how you track the search area. "I keep low and high as the ends of the area that could still hold the target, and mid as the middle."

Third, say why you can throw half away. "If a[mid] is less than the target, every value at or before mid is also too small, so I move low past mid."

Fourth, state the cost and the edge cases. "Each step halves the area, so the time is O(log n) and the space is O(1). I check the empty list, one item, and the first and last index."

A strong candidate also names the traps before the interviewer does. Mention why the loop uses low <= high, and mention that high must start at len(a) - 1. Those details show you have written this function before, and they are easy to check on a whiteboard. Practise the explanation with a timer. It should take about one minute, and it should not need any notes.

When an interviewer changes the problem, do not panic. Ask yourself which of the three questions the problem asks. Is it "is this value present?", "where does this value start?", or "what is the smallest answer that works?" Each of those maps to a version you have already seen in this lesson: the basic search, the lower bound, or binary search on the answer.

Practice

Try each exercise on your own before you open the solution. The hints are short on purpose.

1. Write a function that returns the index where a target should be inserted to keep a sorted list in order. For the list [2, 5, 8] and target 6, the answer is 2. Hint: the lower bound from this lesson already does this, and so does bisect_left.

2. Given the sorted list [1, 2, 2, 2, 5, 7], find the last position of 2. Hint: when you find a match, keep searching to the right by setting low = mid + 1 and remembering the match.

3. How many items equal the target in a sorted list? Use two lower bounds: one for the target and one for the target plus one. Hint: the difference between two lower bounds is a count.

4. How many loop steps does binary search take at most for 1,000 items? Hint: find the smallest power of 2 that is at least 1,000.

5. Trace the search for 16 in [2, 5, 8, 12, 16, 23, 38]. Write low, high and mid for each step. Hint: there are three steps.

6. Write a function that returns the index of the largest value in a sorted list that is less than or equal to x, or -1 if there is none. For [2, 5, 8, 12] and x = 10, the answer is index 2, which holds 8. Hint: find the first index whose value is greater than x, then step back one index.

7. Explain in your own words why high = mid - 1 is safe and high = mid can cause an infinite loop. Hint: think about what happens when low and high are next to each other and a[mid] is less than the target.

8. Write a function is_perfect_square(n) that returns True when n is a perfect square, such as 49, and False otherwise. Hint: use math.isqrt, then compare the result times itself with n.

9. Write a function that returns the smallest whole number x such that x * x is at least n. For n equal to 50, the answer is 8. Hint: this is the mirror of the square root. Find the lower bound on the answer.

10. For the list [2, 5, 8, 12, 16, 23, 38], what does bisect.bisect_left(a, 10) return, and which values would give the same answer? Hint: the result is the index where 10 would be inserted.

Show the answer

1. Use the lower bound. For [2, 5, 8] and 6, the loop moves past 2 and 5 and stops at index 2, which holds 8. Return that index. The same answer comes from bisect.bisect_left([2, 5, 8], 6), which returns 2.

Show the answer

2. Keep a variable last = -1. When a[mid] equals the target, set last = mid and set low = mid + 1. Otherwise follow the normal rule. For [1, 2, 2, 2, 5, 7] the answer is index 3. With bisect, the answer is bisect.bisect_right(a, 2) - 1, which is also 3.

Show the answer

3. Let first be the lower bound of the target and second the lower bound of the target plus one. The count is second - first. For [1, 2, 2, 2, 5, 7] and target 2, first is 1 and second is 4, so the count is 3. With bisect, the same count is bisect.bisect_right(a, 2) - bisect.bisect_left(a, 2).

Show the answer

4. The loop takes at most 10 steps for 1,000 items, because 2 to the power of 10 is 1,024, which is at least 1,000. The program in the cost section showed 10 steps for the worst case.

Show the answer

5. Step 1: low 0, high 6, mid 3, value 12, which is less than 16, so low becomes 4. Step 2: low 4, high 6, mid 5, value 23, which is bigger than 16, so high becomes 4. Step 3: low 4, high 4, mid 4, value 16, found at index 4.

Show the answer

6. Find the first index whose value is greater than x. That is bisect.bisect_right(a, x). If that index is 0, there is no value less than or equal to x, so return -1. Otherwise return the index one less. For [2, 5, 8, 12] and x = 10, the first value greater than 10 is 12 at index 3, so the answer is index 2, which holds 8.

Show the answer

7. When a[mid] is less than the target, mid cannot be the answer, so low = mid + 1 removes it safely. If you wrote low = mid and low and high were next to each other, mid would equal low again. The area would never shrink, and the loop would repeat forever. The same holds for high = mid.

Show the answer

8. Use math.isqrt to get the whole-number square root r, then return r * r == n. Python integers do not overflow, so the multiplication is exact even for very large n.

import math
 
 
def is_perfect_square(n: int) -> bool:
    r = math.isqrt(n)
    return r * r == n

Show the answer

9. Search over x from 0 to n, and keep the smallest x where x * x is at least n. Save the answer when the test passes and move high down to look for a smaller one. For n equal to 50, the test first passes at x equal to 8, because 7 times 7 is 49, which is too small.

def smallest_square_at_least(n: int) -> int:
    low, high = 0, n
    answer = n
    while low <= high:
        mid = low + (high - low) // 2
        if mid * mid >= n:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    return answer

Show the answer

10. The call returns 3. The value 10 would be inserted at index 3, between 8 and 12. Any value from 9 to 12 gives the same answer, because each of them is greater than 8 and no greater than 12. The value 12 itself is found at index 3 too, so bisect_left returns 3 for it.

What you now know

• Divide and conquer splits a problem, solves the pieces, and combines their answers.
• Binary search works only on sorted data, and it halves the search area each step.
• Track the area with low, high and mid, and update with mid + 1 and mid - 1.
• Compute the middle as low + (high - low) // 2. Python integers do not overflow, but this form is the habit to keep for other languages.
• The loop runs in O(log n) time and uses O(1) space. The recursive version uses O(log n) stack space, and Python stops recursion at 1000 calls by default.
• The lower bound finds the first position of a value. Python's bisect module provides it, and binary search on the answer solves questions about numbers.
• Test the boundaries: empty lists, one item, the first and last index, and missing values. Watch for negative indexes, which Python accepts silently.