def sequential_search(a, s):
    for i, element in enumerate(a):
        if element == s:
            return i
    return -1

"""
Explanation: Brute Forces, Secretaries, and Dichotomies
Chapter 11 of Real World Algorithms.


Panos Louridas<br />
Athens University of Economics and Business

Sequential Search
Sequential search is perhaps the most straightforward search method.
We start from the beginning and check each item in turn until we find the one we want.
It can be used for both sorted and unsorted data, but there are much better methods for sorted data.
Here is a straightforward implementation:
End of explanation
"""


import random

a = list(range(1000))
random.shuffle(a)

pos = sequential_search(a, 314)
print(a[pos], 'found at', pos)

pos = sequential_search(a, 1001)
print(pos)

"""
Explanation: Let's check it on a random list:
End of explanation
"""


import timeit

total_elapsed = 0
for i in range(100):
    a = list(range(10000))
    random.shuffle(a)
    start = timeit.default_timer()
    index = sequential_search(a, 314)
    end = timeit.default_timer()
    total_elapsed += end - start
print(total_elapsed)

"""
Explanation: We need not write sequential_search(a, s) in Python. 
If a is a list, we can use a.index(s) instead.
In fact that's what we should do, because it is way faster (we saw that also in Chapter 7).
Here is the timing for our version:
End of explanation
"""


total_elapsed = 0
for i in range(100):
    a = list(range(10000))
    random.shuffle(a)
    start = timeit.default_timer()
    index = a.index(314)
    end = timeit.default_timer()
    total_elapsed += end - start

print(total_elapsed)

"""
Explanation: And here is the timing for the native version (which actually calls a function written in C):
End of explanation
"""


an_item = (1, 2)

another_item = (1, 2)

an_item == another_item

"""
Explanation: Matching, Comparing, Records, Keys
When we are searching for an item in the list, Python performs an equality test between each item and the item we are searching for.
The equality test is performed with the operator ==.
Checking for equality is not the same as checking whether two items are the same.
This is called strict comparison and in Python it is implemented with the operator is.
That means that the following two are equal:
End of explanation
"""


an_item is another_item

"""
Explanation: But they are not the same:
End of explanation
"""


x = 3.14+1.62j
y = 3.14+1.62j
print(x == y)
print(x is y)

"""
Explanation: As another example, let's see what happens with Python's support for complex numbers:
End of explanation
"""


john = {
    'first_name': 'John',
    'surname': 'Doe',
    'passport_no': 'AI892495',
    'year_of_birth': 1990,
    'occupation': 'teacher'
}

jane = {
    'first_name': 'Jane',
    'surname': 'Roe',
    'passport_no': 'AI485713',
    'year_of_birth': 1986,
    'occupation': 'civil engineer'
}

persons = [john, jane]

"""
Explanation: String comparison is must faster than equality checking, but it is not what we usually want to use.
A common idiom for identity checking in Python is checking for None, like if a is None or if a is not None.
In many cases, we hold information for entities in records, which are collections of attributes.
In that case, we want to search for an entity based on a particular attribute that identifies it.
The attribute is called a key.
In Python we can represent records as objects that are instances of a class.
Alternatively, we can represent them as dictionaries.
In fact, Python objects use dictionaries internally.
Let's get a list of two persons.
End of explanation
"""


def sequential_search_m(a, s, matches):
    for i, element in enumerate(a):
        if matches(element, s):
            return i
    return -1

def match_passport(person, passport_no):
    return person['passport_no'] == passport_no

pos = sequential_search_m(persons, 'AI485713', match_passport)
print(persons[pos], 'found at', pos)

"""
Explanation: In this example, the key for our search would be the passport number, because we would like to find the full information for a person with that particular piece of identification.
To do that we could re-implement sequential search so that we provide to it the comparison function.
End of explanation
"""


results = [(i, p) for i, p in enumerate(persons) if p['passport_no'] == 'AI485713']
results

"""
Explanation: Although you would probably use something more Pythonic like:
End of explanation
"""


def transposition_search(a, s):
    for i, item in enumerate(a):
        if item == s:
            if i > 0:
                a[i-1], a[i] = a[i], a[i-1]
                return i-1
            else:
                return i
    return -1

"""
Explanation: Self-Organizing Search
In self-organizing search, we take advantage of an item's popularity to move it to the front of the collection in which we are performing our searches.
In the move-to-front method, when we find an item we move it directly to the front.
In the transposition method, when we find an item we swap it with its predecessor (if any).
We cannot implement directly the algorithms for lists given in the book (that is, algorithm 11.2 and algorithm 11.3) for the simple reason that Python hides the list implementation from us.
Moreover, Python lists are not linked lists. They are variable-length arrays (see the online documentation for details on the implementation of lists in Python).
We can implement algorithm 11.3, which is the transposition method for arrays.
End of explanation
"""


def zipf(n):
    h = 0
    for x in range(1, n+1):
        h += 1/x
    z = [ 1/x * 1/h for x in range(1, n+1) ]
    return z

"""
Explanation: How can we test transposition_search(a, s)?
We need to do some groundwork to emulate a situation of popularity-biased searches.
In particular, we will create a setting where the items we are searching for are governed by Zipf's law.
First, we'll write a function that provides the Zipf probability for $n$ items.
End of explanation
"""


zipf_1000 = zipf(1000)

"""
Explanation: We'll work with 1000 items:
End of explanation
"""


print(sum(zipf_1000))
print(zipf_1000[:20])

"""
Explanation: We can check that they sum up to 1, and see the first 20 of the probabilities.
End of explanation
"""


a = list(range(1000))
random.shuffle(a)
print(a[:20])

"""
Explanation: Again we will be performing our searches on 1000 items, in random order.
End of explanation
"""


b = list(range(1000))
random.shuffle(b)
print(b[:20])

"""
Explanation: We will perform 100000 searches among these items.
We want the searches to follow Zipf's law.
First, we will create another list of 1000 items in random order.
End of explanation
"""


searches = random.choices(b, weights=zipf_1000, k=100000)

"""
Explanation: Then, we will select 100000 items from the second list, using the Zipf probabilities.
That means that we will be selecting the first item with probability zipf_1000[0], the second item with probability zipf_1000[1], and so on.
End of explanation
"""


from collections import Counter

counted = Counter(searches)
counted.most_common(20)


"""
Explanation: Indeed, we can verify that the popularity of items in searches mirrors b:
End of explanation
"""


a_copy = a[:]

total_elapsed = 0
for s in searches:
    start = timeit.default_timer()
    index = transposition_search(a, s)
    end = timeit.default_timer()
    total_elapsed += end - start

print(total_elapsed)
print(a[:20])

"""
Explanation: So, we will perform 100000 searches in the first list, using as keys the items in searches.
Because transposition_search(a, s) changes a, we will keep a copy of it to use it to compare the performance with simple sequential search.
At the end, apart from displaying the time elapsed we will also show the first items of the changed a, to see how popular searches have gone to the beginning.
End of explanation
"""


total_elapsed = 0
for s in searches:
    start = timeit.default_timer()
    index = sequential_search(a_copy, s)
    end = timeit.default_timer()
    total_elapsed += end - start

print(total_elapsed)

"""
Explanation: We will now perform the same searches with a_copy using simple sequential search.
End of explanation
"""


import math

def secretary_search(a):
    # Calculate |a|/n items.
    m = int((len(a) // math.e) + 1)
    
    # Find the best among the first |a|/n.
    c = 0
    for i in range(1, m):
        if a[i] > a[c]:
            c = i
    
    # Get the first that is better from the one
    # we found, if possible.
    for i in range(m, len(a)):
        if a[i] > a[c]:
            return i
    return - 1

"""
Explanation: The Secretary Problem
The secretary problem requires selecting the best item when we have not seen, and we cannot wait to see, the full sets of items.
The solution is an online algorithm. We find the best item among the first $n/e$, where $n$ is the total expected number of items, and $e \approx 2.71828$ is [Euler's number](https://en.wikipedia.org/wiki/E_(mathematical_constant). 
Then we select the first of the remaining items that is better than that. The probability that we'll indeed select the best item is $n/e \approx 37\%$.
Here is how we can do that:
End of explanation
"""


total_found = 0

for i in range(1000):
    a = list(range(1000))
    random.shuffle(a)
    index = secretary_search(a)
    max_index = a.index(max(a))
    if index == max_index:
        total_found += 1

print(f"found  {total_found} out of {i+1}, {100*total_found/(i+1)}%")

"""
Explanation: Does secretary_search(a) find the best item in a about 37% of the time?
To check that, we'll continue working in a similar fashion. We'll perform 1000 searches in 1000 items and see how often we do come up with the best item.
End of explanation
"""


def binary_search(a, item):

    # Initialize borders of search space.
    low = 0
    high = len(a) - 1

    # While the search space is not empty:
    while low <= high:
        # Split the search space in the middle.
        mid = low + (high - low) // 2
        # Compare with midpoint.
        c = (a[mid] > item) - (a[mid] < item)
        # If smaller, repeat on the left half.
        if c < 0:
            low = mid + 1
        # If greater, repeat on the right half.
        elif c > 0:
            high = mid - 1
        # If found, we are done.
        else:
            return mid

    return -1

"""
Explanation: Binary Search
Binary search is the most efficient way to search for an item when the search space is ordered.
It is an iterative algorithm, where in each iteration we split the search space in half.
We start by asking if the search item is in the middle of the search space. Let's assume that the items are ordered in ascending orded.
If it is greater than the item in the middle, we repeat the question on the right part of the search space; it it is smaller, we repeat the question on the left part of the search space. We continue until we find the item, or we cannot perform a split any more.
End of explanation
"""


def binary_search_trace(a, item):

    print("Searching for", item)
    # Initialize borders of search space.
    low = 0
    high = len(a) - 1

    # While the search space is not empty:
    while low <= high:
        # Split the search space in the middle.
        mid = low + (high - low) // 2
        # Compare with midpoint.
        c = (a[mid] > item) - (a[mid] < item)
        print(f"({low}, {a[low]}), ({mid}, {a[mid]}), ({high}, {a[high]})")
        
        # If smaller, repeat on the left half.
        if c < 0:
            low = mid + 1
        # If greater, repeat on the right half.
        elif c > 0:
            high = mid - 1
        # If found, we are done.
        else:
            return mid

    return -1

a = [4, 10, 31, 65, 114, 149, 181, 437,
     480, 507, 551, 613, 680, 777, 782, 903] 

binary_search_trace(a, 149)
binary_search_trace(a, 181)
binary_search_trace(a, 583)
binary_search_trace(a, 450)
binary_search_trace(a, 3)


"""
Explanation: In Python 3 there is no cmp(x, y) function that compares x and y and returns -1, 0, or 1, if x &gt; y, x == y, or x &lt; y, respectively. We use the 
python
(x &gt; y) - (y &lt; x)
idiom instead.
Note also the line where we calculate the midpoint:
python
mid = low + (high - low) // 2
This guards against overflows. In Python that is not necessary, because there is no upper limit in integers, so it could be:
python
mid = (low + high) // 2
However, this is a problem in most other languages, so we'll stick with the foolproof version.
To see how binary search works we can add some tracing information in binary_search(a, item):
End of explanation
"""


def binary_search_count(a, item):

    # Initialize borders of search space.
    low = 0
    high = len(a) - 1
    
    i = 0
    # While the search space is not empty:
    while low <= high:
        i += 1
        # Split the search space in the middle.
        mid = low + (high - low) // 2
        # Compare with midpoint.
        c = (a[mid] > item) - (a[mid] < item)
        
        # If smaller, repeat on the left half.
        if c < 0:
            low = mid + 1
        # If greater, repeat on the right half.
        elif c > 0:
            high = mid - 1
        # If found, we are done.
        else:
            return (i, mid)

    return (i, -1)

"""
Explanation: Binary search is very efficient&mdash;in fact, it is as efficient as a search method can be (there is a smalll caveat here, concerning searching in quantum computers, but we can leave that aside).
If have have $n$ items, it will complete the search in $O(\lg(n))$.
Once again, we can verify that theory agrees with practice. We will perform 1000 searches, 500 of them successful and 500 of them unsuccessful and count the average number of iterations required. To do that, we'll change binary_search(a, item) so that it also returns the number of iterations.
End of explanation
"""


num_range = 1000000
# Get 1000 random numbers from 0 to 999999.
a = random.sample(range(num_range), k=1000)
# Select 500 from them for our matching searches.
existing = random.sample(a, k=500)
# Select another 500 random numbers in the range, 
# not in the set a, for our non-matching searches
non_existing = random.sample(set(range(num_range)) - set(a), k=500)

# Verify that the matching and non-matchin sets are distinct.
print(set(existing) & set(non_existing))

"""
Explanation: We build up our test suite. Our items will be 1000 random numbers in the range from 0 to 999,999.
We will select 500 of them to perform matching searches, and another 500, not in them, to perform non-matching searches.
End of explanation
"""


total_iters = 0
for matching, non_matching in zip(existing, non_existing):
    matching_iters, _ = binary_search_count(a, matching)
    non_matching_iters, _ = binary_search_count(a, non_matching)
    total_iters += (matching_iters + non_matching_iters)
    
print(f"Average iterations:", total_iters / (len(existing) + len(non_existing)))
print(f"lg(1000) = {math.log(1000, 2)}")

"""
Explanation: So now we can see how the average number of iterations in practice fares compared to what predicted by theory.
End of explanation
"""


