-1

I do not want the answer. Could some one please give me a hint on how to approach this problem? Thanks.

Exercise 10
To check whether a word is in the word list, you could use the in operator, but it would be slow because it searches through the words in order. Because the words are in alphabetical order, we can speed things up with a bisection search (also known as binary search), which is similar to what you do when you look a word up in the dictionary. You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the list. If so, you search the first half of the list the same way. Otherwise you search the second half.

Either way, you cut the remaining search space in half. If the word list has 113,809 words, it will take about 17 steps to find the word or conclude that it’s not there.

Write a function called in_bisect that takes a sorted list and a target value and returns the index of the value in the list if it’s there, or None if it’s not.

Mati Sandacz
  • 29
  • 2
  • 2
    The "hint" is actually spelled out in your task: "You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the list. If so, you search the first half of the list the same way. Otherwise you search the second half." Do you have a specific problem with putting that into code? What have you tried? – Amadan Jan 31 '17 at 05:16
  • Yes sorry. My problem was translating into code. – Mati Sandacz Jan 31 '17 at 05:17
  • That's a very general problem, and the only way to help you is to code it for you. That's why I ask - what is the *specific* problem you have? (Also, "Write a function called in_bisect that takes a sorted list and a target value and returns the index of the value in the list if it’s there, or None if it’s not." is another "hint", giving you at least the skeleton of the function to implement. Start there.) You can edit your OP to add the code you produced, or to ask more specific questions. – Amadan Jan 31 '17 at 05:18
  • get `x = len(sorted_list)/2` and check `sorted_list[x]`. After that get left part of list `sorted_list = sorted_list[:x]` or right part `sorted_list = sorted_list[x+1:]` and repeat everything. – furas Jan 31 '17 at 05:20
  • You can find plenty of examples on stackoverflow e.g. http://stackoverflow.com/questions/9501337/binary-search-algorithm-in-python Try alternative keyword `binary search` and you can get more hit from your google search – Anthony Kong Jan 31 '17 at 05:33
  • Okay thanks guys i think i solved it. – Mati Sandacz Jan 31 '17 at 06:20

1 Answers1

-1

There's a python library for doing this: the bisect library.

There's a general programming paradigm that is called for in this situation. Given the problem you've been given, I'm guessing that this paradigm has been discussed in class. It starts with an "r".

Once you get it, it will seem pretty cool.

Alex L
  • 1,114
  • 8
  • 11