FilesExpand file tree

 master

/

inlist.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

79 lines (53 loc) · 1.74 KB

 master

/

inlist.py

Top

File metadata and controls

• Code
• Blame

79 lines (53 loc) · 1.74 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

"""This module contains a code example related to

Think Python, 2nd Edition

by Allen Downey

http://thinkpython2.com

Copyright 2015 Allen Downey

License: http://creativecommons.org/licenses/by/4.0/

"""

from __future__ import print_function, division

import bisect

def make_word_list():

"""Reads lines from a file and builds a list using append.

returns: list of strings

"""

word_list = []

fin = open('words.txt')

for line in fin:

word = line.strip()

word_list.append(word)

return word_list

def in_bisect(word_list, word):

"""Checks whether a word is in a list using bisection search.

Precondition: the words in the list are sorted

word_list: list of strings

word: string

returns: True if the word is in the list; False otherwise

"""

if len(word_list) == 0:

return False

i = len(word_list) // 2

if word_list[i] == word:

return True

if word_list[i] > word:

# search the first half

return in_bisect(word_list[:i], word)

else:

# search the second half

return in_bisect(word_list[i+1:], word)

def in_bisect_cheat(word_list, word):

"""Checks whether a word is in a list using bisection search.

Precondition: the words in the list are sorted

word_list: list of strings

word: string

"""

i = bisect.bisect_left(word_list, word)

if i == len(word_list):

return False

return word_list[i] == word

if __name__ == '__main__':

word_list = make_word_list()

for word in ['aa', 'alien', 'allen', 'zymurgy']:

print(word, 'in list', in_bisect(word_list, word))

for word in ['aa', 'alien', 'allen', 'zymurgy']:

print(word, 'in list', in_bisect_cheat(word_list, word))