CODEWITHSUNDEEP
pythonbinary-search
Manu
Manu

Reputation: 319

How does binary search work?

I am learning python through this website.

It's a fantastic resource, but when he explains binary searches I am left a little confused.

This is the code he supplies to search through a text file of super-villain names:

file = open("super_villains.txt")

name_list = []
for line in file:
    line = line.strip()
    name_list.append(line)

file.close()

# Binary search
key = "Morgiana the Shrew"
lower_bound = 0
upper_bound = len(name_list)-1
found = False
while lower_bound <= upper_bound and not found:
    middle_pos = (lower_bound+upper_bound) // 2
    if name_list[middle_pos] < key:
        lower_bound = middle_pos + 1
    elif name_list[middle_pos] > key:
        upper_bound = middle_pos - 1
    else:
        found = True

if found:
    print("The name is at position", middle_pos)
if not found:
    print("The name was not in the list.")

This is the part that has left me confused: if name_list[middle_pos] < key: How could python possibly know if a certain position in the index is greater or lesser than the position of the key, without already knowing the position of the key we're looking for?

This feels like a dumb question, but I don't understand how you can compare two positions in an array when we don't know one of them.

Upvotes: 1

Views: 156

Answers (3)

Open AI - Opting Out
Open AI - Opting Out

Reputation: 24133

name_list[middle_pos] is going to be some value such as Ratigan the Rat. In your example key is Morgiana the Shrew.

The comparison name_list[middle_pos] < key will decide whether Ratigan is before Morgiana. As he isn't (alphabetically), we then narrow our search to the range of names before him, and chop it in half. Then ask the question again, and narrow the range.

You keep narrowing the range until there is only one value left. It is either correct or not. If not then Morgiana isn't in the list at all. Or we've found her index.

Upvotes: 2

Chad S.
Chad S.

Reputation: 6633

It assumes that the list name_list is in sorted order. Then if the name located at middle_pos occurs alphabetically before the name we are searching for (key in this case) we know we can skip all the names from lower_bound to middle_pos.

Upvotes: 1

R Nar
R Nar

Reputation: 5515

One key thing for binary searches is that it is searching through a sorted list, in this case, I believe that it is assuming that is in sorted alphabetically.

With this in mind, that if statement is actually comparing strings, not numbers which means that it is looking whether the current key is before or after the current middle pos. Then once it finds out, it will half the positions until it has found the position of the key.

Upvotes: 2

Related Questions