CODEWITHSUNDEEP
python-3.xalgorithmsearch
DonCarleone
DonCarleone

Reputation: 829

Binary Search seems to return random result

Before I start, I'm not asking about binary search, or how to solve this problem.
My question is:
Why am I getting weird results. What's going on under the hood to cause these results?
Here goes:
I'm trying to write an algorithm to search an ordered list of words. The only catch is, the lexigraphically ordered list starts somewhere in the middle of the alphabet, and I need to find the rotation point (the index of the "smallest" word). To break the problem down, I decided I'll first search for the biggest word, which will always be right before the smallest, then I'll worry about the index.
I did this.
But then I started noticing weird results and got a little sidetracked.
I'm using an online interpreter and somehow I'm getting seemingly random results. I'm getting zi, yi, xi, wi,vo and sometimes d
Here's what my list looks like:
words = list({'vo', 'wi', 'xi', 'yi', 'zi', 'ai', 'bi', 'ci', 'd'})

and here's what my code looks like

low = 0
high = len(words)
mid = (high-low) // 2 + low
biggest_word = words[0]
while high-low > 1:
    if words[mid] > biggest_word:
        biggest_word = words[mid]
        high = mid
    else:
        low = mid
    mid = (high-low) // 2 + low
print (biggest_word)

Update: I've found that this issue only occurs in Python3. Python2 yields consistent results.

Upvotes: 0

Views: 58

Answers (1)

FoolsWisdom
FoolsWisdom

Reputation: 1051

The syntax list({'vo', 'wi', 'xi', 'yi', 'zi', 'ai', 'bi', 'ci', 'd'}) first creates a set, then makes a list out of that set. A set is an unordered data structure, so the order in the list is random. It seems that in python 2 a set keeps insertion order nevertheless, but python 3 it does not.

Upvotes: 2

Related Questions