Python - Searching and Sorting(linear searches, duplicate values)

Practical Programming
An Introduction to Computer Science
Using Python 3
(Pragmatic Programmers)
(Pragmatic Bookshelf)
Paul Gries (著) Jennifer Campbell (著)
Jason Montojo (著) Lynn Beighley (編集)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Python 3.4 (プログラミング言語)

Practical Programming: An Introduction to Computer Science Using Python 3 (Pragmatic Programmers) (Paul Gries (著)、Jennifer Campbell (著)、Jason Montojo (著)、Lynn Beighley (編集)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、13.7(Exercises), 2.を解いてみる。

13.7(Exercises), 2.

コード(BBEdit)

sample2.py

#!/usr/bin/env python3
#-*- coding: utf-8 -*-

# 重複している場合は、より右側の値のインデックスが見つかる
# while loop
def linearSeardh1(lst, value):
    '''(list, object) -> int
    Return the index of the last occurance of value in lst, or return -1
    if value i not in lst.
    >>> linearSeardh1([2, 5, 5, -1], 5)
    2
    >>> linearSeardh1([2, 4, 2], 2)
    2
    '''
    i = len(lst) -1

    while i != -1 and lst[i] != value:
        i -= 1

    if i == -1:
        return -1
    else:
        return i

# for loop
def linearSeardh2(lst, value):
    '''(list, object) -> int
    Return the index of the last occurance of value in lst, or return -1
    if value i not in lst.
    >>> linearSeardh2([2, 5, 5, -1], 5)
    2
    >>> linearSeardh2([2, 4, 2], 2)
    2
    '''
    for i in range(len(lst) - 1, -1, -1):
        if lst[i] == value:
            return i
    return -1

# sentinel search    
def linearSeardh3(lst, value):
    '''(list, object) -> int
    Return the index of the last occurance of value in lst, or return -1
    if value i not in lst.
    >>> linearSeardh3([2, 5, 5, -1], 5)
    2
    >>> linearSeardh3([2, 4, 2], 2)
    2
    '''
    lst.insert(0, value)

    i = len(lst) - 1
    while lst[i] != value:
        i -= 1
    
    lst.pop(0)

    if i == 0:
        return -1
    else:
        return i - 1

if __name__ == '__main__':
    import doctest
    doctest.testmod()

入出力結果(Terminal, IPython)

$ ./sample2.py -v
Trying:
    linearSeardh1([2, 5, 5, -1], 5)
Expecting:
    2
ok
Trying:
    linearSeardh1([2, 4, 2], 2)
Expecting:
    2
ok
Trying:
    linearSeardh2([2, 5, 5, -1], 5)
Expecting:
    2
ok
Trying:
    linearSeardh2([2, 4, 2], 2)
Expecting:
    2
ok
Trying:
    linearSeardh3([2, 5, 5, -1], 5)
Expecting:
    2
ok
Trying:
    linearSeardh3([2, 4, 2], 2)
Expecting:
    2
ok
1 items had no tests:
    __main__
3 items passed all tests:
   2 tests in __main__.linearSeardh1
   2 tests in __main__.linearSeardh2
   2 tests in __main__.linearSeardh3
6 tests in 4 items.
6 passed and 0 failed.
Test passed.
$