# Using the bisect Module

**00:00**
In this lesson, I’m going to show you how to use the `bisect`

module, which is in-built in Python. And the reason I’m showing this to you before showing you how to implement binary search on your own in Python is just to impress upon you the importance of using library modules that are verified and vetted for performance and security before you necessarily reinvent the wheel. Now, of course, there are reasons to actually implement binary search on your own, and I’ll talk about those when I get into doing so. But for the moment, let’s take a look at `bisect`

.

**00:33**
Now, the `bisect`

module performs the same work as a binary search function, but it does it in a little bit of an interesting way. What `bisect()`

is concerned with is finding the index at which an item could be inserted in the list to maintain the sorted order.

**00:50**
So, the `bisect()`

function, aka `bisect_right()`

—because this is really just an alias for `bisect_right()`

—when you call it on an item that is in the list, it will actually return the index *after* that item, because it’s the index at which you could insert a new copy of this item, if you wanted to maintain sorted order. And in the case of duplicates, it returns the rightmost index.

**01:12**
So `bisect_left()`

is actually the function that will generate the index of existing items in the list, because it returns the leftmost possible index that you could insert an item at to maintain sorted order. Now, I realize that may not be entirely clear, but I’ll demonstrate in the REPL how this works, and I think it will become a lot more obvious.

**01:32**
And then the `insort`

functions are essentially just functions that call `bisect()`

and then actually insert the item at the index found. So, there’s an `insort_right()`

and an `insort_left()`

just like there’s a `bisect_right()`

and `bisect_left()`

.

**01:46**
So, let’s see these in action.

**01:49**
Here, I’ve imported `bisect`

, and I’ve actually defined beforehand a list of fruits that has an `'apple'`

, three copies of the string `'banana'`

, then `'orange'`

, and `'pineapple'`

. So as you can see, this is in sorted order—`'a'`

, `'b'`

, `'o'`

, `'p'`

—and so that means that I can use `bisect`

. An important feature of `bisect`

is that it doesn’t enforce this sorted order, so if you call it on a list that’s not already sorted, it will probably give you an odd behavior. And so you don’t want to do that.

**02:20**
Let’s see what happens when I call `bisect.bisect()`

on the string `'banana'`

in the `fruits`

array. So, `param a`

, `param x`

—the list and then the actual item to find—so `fruits`

and then `"banana"`

.

**02:37**
It’s going to return the index `4`

. `0`

, `1`

, `2`

, `3`

, and then `4`

. So it says, “If I insert `'banana'`

at index `4`

, pushing these two over an index, then I’ll still have a list that’s in sorted order.” And this is exactly the same as `bisect.bisect_right()`

—It actually returns exactly the same thing—but if I call `bisect_left()`

, I get a bit of a different behavior. I get the index `1`

, which interestingly enough is the first index of that string in the list.

**03:04**
Because I could insert at this index, and now that copy of `'banana'`

would be the leftmost instance of `'banana'`

and the whole list would still be in sorted order.

**03:13**
So that’s the key to understanding `bisect`

, is it’s concerned with “Where can I put stuff to make sure that this list maintains sorted order?” And when there are duplicate copies, that’ll be on either side with `bisect_left()`

and `bisect_right()`

.

**03:25**
Interestingly enough, if I call `bisect_right()`

and then I subtract the call on `bisect_left()`

with the same parameters,

**03:34**
then I’ll actually get the number of occurrences of this item here, which is in fact `3`

. So that’s kind of a cool, random feature of `bisect`

that you might be able to use.

**03:44**
So now, if I call `bisect.insort`

and let’s call `bisect.insort_left()`

of `fruits`

, and then let’s say `"kiwi"`

just for fun, and see what it does.

**03:56**
So, `bisect.insort_left(fruits, "kiwi")`

. If I print out `fruits`

, it will put `'kiwi'`

right after `'banana'`

.

**04:03**
Now let’s put in one more copy of `"banana"`

here,

**04:09**
and you’ll see—of course it won’t be entirely clear what side that it actually put it on because these are strings, so there’s no obvious way to see the differences here, but it did in fact put it on the left. So now you might be wondering “Why, in fact, are there these `bisect_right()`

, and `bisect_left()`

and `insort_right()`

and `insort_left()`

if it’s never going to be obvious that you’ve actually put it on either side?” Well, the reason for that is when you start to have more complex objects, you might have objects that compare equal to one another, but are in fact different objects. That is, they occupy different memory locations, but they consist of the same data that’s compared for equality.

**04:51**
And if you’re interested, I’d encourage you to check out the tutorials on Real Python about the `is`

and equals (`==`

) comparison operators, because they’ll give you a little bit more context as to why this distinction between `insort_left()`

and `insort_right()`

can actually be important in various cases.

**05:07**
But for now, just know that that is what these functions do, and this is how it looks in practice. In the next lesson, I’ll show you how to actually implement a binary search on your own without any help from library modules.

Become a Member to join the conversation.