How to impliment a binary search on a list created from a file

Question

This is my first post, please be gentle. I'm attempting to sort some files into ascending and descending order. Once I have sorted a file, I am storing it in a list which is assigned to a variable. The user is then to choose a file and search for an item. I get an error message....

TypeError: unorderable types; int() < list()

.....when ever I try to search for an item using the variable of my sorted list, the error occurs on line 27 of my code. From research, I know that an int and list cannot be compared, but I cant for the life of me think how else to search a large (600) list for an item. At the moment I'm just playing around with binary search to get used to it. Any suggestions would be appreciated.

year = []
    with open("Year_1.txt") as file:
        for line in file:
            line = line.strip()
            year.append(line)

def selectionSort(alist):
   for fillslot in range(len(alist)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if alist[location]>alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False
    while first<=last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
        found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    return found

selectionSort(year)
testlist = []
testlist.append(year)
print(binarySearch(testlist, 2014))

Year_1.txt file consists of 600 items, all years in the format of 2016. They are listed in descending order and start at 2017, down to 2013. Hope that makes sense.

Welcome to Stackoverflow! Can you add the content of ```Year_1.txt``` file? — arshovon, May 10 '17 at 16:31
Idk if its a copy & paste thing but the lines `if alist[midpoint] == item: found = True` are not indented correctly in your post — patrick, May 10 '17 at 16:33
`testlist = []; testlist.append(year)` - what the heck? Why is `testlist` even a thing? — user2357112, May 10 '17 at 16:33
Your code expects strings. `2014` on your last line is a number. Try calling it with `"2014"`. — VBB, May 10 '17 at 16:37
You should try to use the standard python library instead of trying to implement by yourself. see https://docs.python.org/3/library/bisect.html — Setop, May 10 '17 at 16:44
Thanks for all replies. can't use pythons built in library, its a Uni assignment. I'm 45 and decided to go back to school. — Beginningbob, May 10 '17 at 16:49
It would be better to miss out the part with the files and the sort, and just use a list of test data, already sorted. See how to create a [mcve]. — Peter Wood, May 10 '17 at 16:54

Jim Dennis · Answer 1 · 2017-05-10T17:16:42.430

Is there some reason you're not using the Python: bisect module?

Something like:

import bisect

sorted_year = list()
for each in year:
    bisect.insort(sorted_year, each)

... is sufficient to create the sorted list. Then you can search it using functions such as those in the documentation.

(Actually you could just use year.sort() to sort the list in-place ... bisect.insort() might be marginally more efficient for building the list from the input stream in lieu of your call to year.append() ... but my point about using the `bisect module remains).

Also note that 600 items is trivial for modern computing platforms. Even 6,000 won't take but a few milliseconds. On my laptop sorting 600,000 random integers takes about 180ms and similar sized strings still takes under 200ms.

So you're probably not gaining anything by sorting this list in this application at that data scale.

On the other hand Python also includes a number of modules in its standard libraries for managing structured data and data files. For example you could use Python: SQLite3.

Using this you'd use standard SQL DDL (data definition language) to describe your data structure and schema, SQL DML (data manipulation language: INSERT, UPDATE, and DELETE statements) to manage the contents of the data and SQL queries to fetch data from it. Your data can be returned sorted on any column and any mixture of ascending and descending on any number of columns with the standard SQL ORDER BY clauses and you can add indexes to your schema to ensure that the data is stored in a manner to enable efficient querying and traversal (table scans) in any order on any key(s) you choose.

Because Python includes SQLite in its standard libraries, and because SQLite provides SQL client/server semantics over simple local files ... there's almost no downside to using it for structured data. It's not like you have to install and maintain additional software, servers, handle network connections to a remote database server nor any of that.

Not allowed to use python built in modules Jim. thanks for your reply. — Beginningbob, May 10 '17 at 17:01
Okay. So this presumably is some sort of homework assignment. It's best to clarify that upfront when posting your questions. — Jim Dennis, May 10 '17 at 17:18

score 0 · Answer 2 · edited May 23 '17 at 12:26

I'm going to walk through some steps before getting to the answer.

You need to post a [mcve]. Instead of telling us to read from "Year1.txt", which we don't have, you need to put the list itself in the code. Do you NEED 600 entries to get the error in your code? No. This is sufficient:

year = ["2001", "2002", "2003"]

If you really need 600 entries, then provide them. Either post the actual data, or

year = [str(x) for x in range(2017-600, 2017)]

The code you post needs to be Cut, Paste, Boom - reproduces the error on my computer just like that.

selectionSort is completely irrelevant to the question, so delete it from the question entirely. In fact, since you say the input was already sorted, I'm not sure what selectionSort is actually supposed to do in your code, either. :)

Next you say testlist = [].append(year). USE YOUR DEBUGGER before you ask here. Simply looking at the value in your variable would have made a problem obvious.

How to append list to second list (concatenate lists)

Fixing that means you now have a list of things to search. Before you were searching a list to see if 2014 matched the one thing in there, which was a complete list of all the years.

Now we get into binarySearch. If you look at the variables, you see you are comparing the integer 2014 with some string, maybe "1716", and the answer to that is useless, if it even lets you do that (I have python 2.7 so I am not sure exactly what you get there). But the point is you can't find the integer 2014 in a list of strings, so it will always return False.

If you don't have a debugger, then you can place strategic print statements like

print ("debug info: binarySearch comparing ", item, alist[midpoint])

Now here, what VBB said in comments worked for me, after I fixed the other problems. If you are searching for something that isn't even in the list, and expecting True, that's wrong. Searching for "2014" returns True, if you provide the correct list to search. Alternatively, you could force it to string and then search for it. You could force all the years to int during the input phase. But the int 2014 is not the same as the string "2014".

How to impliment a binary search on a list created from a file

2 Answers2