# lec10prob2.py
 
# In lecture, we saw a version of linear search that used the fact that a set
# of elements is sorted in increasing order. Here is the code from lecture:
 
def search(L, e):
    for i in range(len(L)):
        if L[i] == e:
            return True
        if L[i] > e:
            return False
    return False
 
# Consider the following code, which is an alternative version of search.
 
def search1(L, e):
    for i in L:
        if i == e:
            return True
        if i > e:
            return False
    return False
 
# Which of the following statements is correct? You may assume that each
# function is tested with a list L whose elements are sorted in increasing
# order; for simplicity, assume L is a list of positive integers.
#
# - search and search1 return the same answers
# - search and search1 return the same answers provided L is non-empty
# - search and search1 return the same answers provided L is non-empty and e is in L
# - search and search1 do not return the same answers
# - search and search1 return the same answers for lists of length 0 and 1 only
 
# Sample list and calls to both search and search1 with different lists
# to match conditions in above possible answers
 
# Search for a number in list
print(search([2, 5, 7, 10, 15, 27, 35, 44], 35))
print(search1([2, 5, 7, 10, 15, 27, 35, 44], 35))
print
 
# Search for a number not in list
print(search([2, 5, 7, 10, 15, 27, 35, 44], 3))
print(search1([2, 5, 7, 10, 15, 27, 35, 44], 3))
print
 
# Search for a number in an empty list
print(search([], 5))
print(search1([], 5))
print
 
# Search for a number in a single element list
print(search([5], 5))
print(search1([5], 5))
print

IyBsZWMxMHByb2IyLnB5CgojIEluIGxlY3R1cmUsIHdlIHNhdyBhIHZlcnNpb24gb2YgbGluZWFyIHNlYXJjaCB0aGF0IHVzZWQgdGhlIGZhY3QgdGhhdCBhIHNldAojIG9mIGVsZW1lbnRzIGlzIHNvcnRlZCBpbiBpbmNyZWFzaW5nIG9yZGVyLiBIZXJlIGlzIHRoZSBjb2RlIGZyb20gbGVjdHVyZToKCmRlZiBzZWFyY2goTCwgZSk6CiAgICBmb3IgaSBpbiByYW5nZShsZW4oTCkpOgogICAgICAgIGlmIExbaV0gPT0gZToKICAgICAgICAgICAgcmV0dXJuIFRydWUKICAgICAgICBpZiBMW2ldID4gZToKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCiAgICByZXR1cm4gRmFsc2UKCiMgQ29uc2lkZXIgdGhlIGZvbGxvd2luZyBjb2RlLCB3aGljaCBpcyBhbiBhbHRlcm5hdGl2ZSB2ZXJzaW9uIG9mIHNlYXJjaC4KCmRlZiBzZWFyY2gxKEwsIGUpOgogICAgZm9yIGkgaW4gTDoKICAgICAgICBpZiBpID09IGU6CiAgICAgICAgICAgIHJldHVybiBUcnVlCiAgICAgICAgaWYgaSA+IGU6CiAgICAgICAgICAgIHJldHVybiBGYWxzZQogICAgcmV0dXJuIEZhbHNlCgojIFdoaWNoIG9mIHRoZSBmb2xsb3dpbmcgc3RhdGVtZW50cyBpcyBjb3JyZWN0PyBZb3UgbWF5IGFzc3VtZSB0aGF0IGVhY2gKIyBmdW5jdGlvbiBpcyB0ZXN0ZWQgd2l0aCBhIGxpc3QgTCB3aG9zZSBlbGVtZW50cyBhcmUgc29ydGVkIGluIGluY3JlYXNpbmcKIyBvcmRlcjsgZm9yIHNpbXBsaWNpdHksIGFzc3VtZSBMIGlzIGEgbGlzdCBvZiBwb3NpdGl2ZSBpbnRlZ2Vycy4KIwojIC0gc2VhcmNoIGFuZCBzZWFyY2gxIHJldHVybiB0aGUgc2FtZSBhbnN3ZXJzCiMgLSBzZWFyY2ggYW5kIHNlYXJjaDEgcmV0dXJuIHRoZSBzYW1lIGFuc3dlcnMgcHJvdmlkZWQgTCBpcyBub24tZW1wdHkKIyAtIHNlYXJjaCBhbmQgc2VhcmNoMSByZXR1cm4gdGhlIHNhbWUgYW5zd2VycyBwcm92aWRlZCBMIGlzIG5vbi1lbXB0eSBhbmQgZSBpcyBpbiBMCiMgLSBzZWFyY2ggYW5kIHNlYXJjaDEgZG8gbm90IHJldHVybiB0aGUgc2FtZSBhbnN3ZXJzCiMgLSBzZWFyY2ggYW5kIHNlYXJjaDEgcmV0dXJuIHRoZSBzYW1lIGFuc3dlcnMgZm9yIGxpc3RzIG9mIGxlbmd0aCAwIGFuZCAxIG9ubHkKCiMgU2FtcGxlIGxpc3QgYW5kIGNhbGxzIHRvIGJvdGggc2VhcmNoIGFuZCBzZWFyY2gxIHdpdGggZGlmZmVyZW50IGxpc3RzCiMgdG8gbWF0Y2ggY29uZGl0aW9ucyBpbiBhYm92ZSBwb3NzaWJsZSBhbnN3ZXJzCgojIFNlYXJjaCBmb3IgYSBudW1iZXIgaW4gbGlzdApwcmludChzZWFyY2goWzIsIDUsIDcsIDEwLCAxNSwgMjcsIDM1LCA0NF0sIDM1KSkKcHJpbnQoc2VhcmNoMShbMiwgNSwgNywgMTAsIDE1LCAyNywgMzUsIDQ0XSwgMzUpKQpwcmludAoKIyBTZWFyY2ggZm9yIGEgbnVtYmVyIG5vdCBpbiBsaXN0CnByaW50KHNlYXJjaChbMiwgNSwgNywgMTAsIDE1LCAyNywgMzUsIDQ0XSwgMykpCnByaW50KHNlYXJjaDEoWzIsIDUsIDcsIDEwLCAxNSwgMjcsIDM1LCA0NF0sIDMpKQpwcmludAoKIyBTZWFyY2ggZm9yIGEgbnVtYmVyIGluIGFuIGVtcHR5IGxpc3QKcHJpbnQoc2VhcmNoKFtdLCA1KSkKcHJpbnQoc2VhcmNoMShbXSwgNSkpCnByaW50CgojIFNlYXJjaCBmb3IgYSBudW1iZXIgaW4gYSBzaW5nbGUgZWxlbWVudCBsaXN0CnByaW50KHNlYXJjaChbNV0sIDUpKQpwcmludChzZWFyY2gxKFs1XSwgNSkpCnByaW50