.ipynb .pdf

repository open issue suggest edit

Binder

Contents

1 Binary Search

QUESTION: Alice has some cards with numbers written on them. She arranges the cards in decreasing order, and lays them out face down in a sequence on a table. She challenges Bob to pick out the card containing a given number by turning over as few cards as possible. Write a function to help Bob locate the card.

0.1 Example inputs & outputs for test

To solve a data structure problem, the first step is to come up with some examples inputs&outputs, covered all edge cases, in order to test our algorithm.

# test inputs & outputs
tests = []

# query occurs in the middle 
tests.append({
    'input': {
        'cards': [13, 11, 10, 7, 4, 3, 1, 0],
        'query': 1
    },
    'output': 6
})

# query is the first element
tests.append({
    'input': {
        'cards': [4, 2, 1, -1],
        'query': 4
    },
    'output': 0
})

# query is the last element
tests.append({
    'input': {
        'cards': [3, -1, -9, -127],
        'query': -127
    },
    'output': 3
})

# cards contains just one element, query
tests.append({
    'input': {
        'cards': [6],
        'query': 6
    },
    'output': 0 
})

# cards does not contain query, return -1
tests.append({
    'input': {
        'cards': [9, 7, 5, 2, -9],
        'query': 4
    },
    'output': -1
})

# cards is empty, return -1
tests.append({
    'input': {
        'cards': [],
        'query': 7
    },
    'output': -1
})

# numbers can repeat in cards
tests.append({
    'input': {
        'cards': [8, 8, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0],
        'query': 3
    },
    'output': 7
})

# query occurs multiple times, return the first location
tests.append({
    'input': {
        'cards': [8, 8, 6, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0],
        'query': 6
    },
    'output': 2
})

tests

[{'input': {'cards': [13, 11, 10, 7, 4, 3, 1, 0], 'query': 1}, 'output': 6},
 {'input': {'cards': [4, 2, 1, -1], 'query': 4}, 'output': 0},
 {'input': {'cards': [3, -1, -9, -127], 'query': -127}, 'output': 3},
 {'input': {'cards': [6], 'query': 6}, 'output': 0},
 {'input': {'cards': [9, 7, 5, 2, -9], 'query': 4}, 'output': -1},
 {'input': {'cards': [], 'query': 7}, 'output': -1},
 {'input': {'cards': [8, 8, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 3},
  'output': 7},
 {'input': {'cards': [8, 8, 6, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0],
   'query': 6},
  'output': 2}]

0.2 Time Complexity & Space Complexity

Complexity: always refers to the worst-case complexity (i.e. the highest possible time/space taken by the program/algorithm to process an input)
Time complexity: also called the running time of the algorithm
Space complexity: numbers of variables we need to iterate through the array

1.1 linear search

linear search: 按顺序比较每一个位置的元素和query是否相同，相同则返回position

# linear search
def locate_card_linear(cards, query):
    position = 0
    while position < len(cards):
        if cards[position] == query:
            return position
        position += 1
    return -1

from jovian.pythondsa import evaluate_test_cases
evaluate_test_cases(locate_card_linear, tests)

TEST CASE #0

Input:
{'cards': [13, 11, 10, 7, 4, 3, 1, 0], 'query': 1}

Expected Output:
6


Actual Output:
6

Execution Time:
0.007 ms

Test Result:
PASSED


TEST CASE #1

Input:
{'cards': [4, 2, 1, -1], 'query': 4}

Expected Output:
0


Actual Output:
0

Execution Time:
0.003 ms

Test Result:
PASSED


TEST CASE #2

Input:
{'cards': [3, -1, -9, -127], 'query': -127}

Expected Output:
3


Actual Output:
3

Execution Time:
0.004 ms

Test Result:
PASSED


TEST CASE #3

Input:
{'cards': [6], 'query': 6}

Expected Output:
0


Actual Output:
0

Execution Time:
0.003 ms

Test Result:
PASSED


TEST CASE #4

Input:
{'cards': [9, 7, 5, 2, -9], 'query': 4}

Expected Output:
-1


Actual Output:
-1

Execution Time:
0.005 ms

Test Result:
PASSED


TEST CASE #5

Input:
{'cards': [], 'query': 7}

Expected Output:
-1


Actual Output:
-1

Execution Time:
0.002 ms

Test Result:
PASSED


TEST CASE #6

Input:
{'cards': [8, 8, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 3}

Expected Output:
7


Actual Output:
7

Execution Time:
0.005 ms

Test Result:
PASSED


TEST CASE #7

Input:
{'cards': [8, 8, 6, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 6}

Expected Output:
2


Actual Output:
2

Execution Time:
0.004 ms

Test Result:
PASSED


SUMMARY

TOTAL: 8, PASSED: 8, FAILED: 0

[(6, True, 0.007),
 (0, True, 0.003),
 (3, True, 0.004),
 (0, True, 0.003),
 (-1, True, 0.005),
 (-1, True, 0.002),
 (7, True, 0.005),
 (2, True, 0.004)]

Time complexity of linear search is O(N), because the worst case of the run time could be \(cN\), where \(N\) is the numbers of cards and \(c\) is the runtime of one iteration.
Space complexity of linear serach is O(1), because we only need 1 variable position in the iteration.

1.2 Binary Search

Binary Search 原理上与二分法相同，由于本身是按照顺序排列，因此每次循环只需要比较query和middle的数字进行比较，而后不断进行二分法式的比较，最终获得output

# binary search
def locate_card_binary(cards, query):
    '''Locate the query in the cards with binary search method'''
    lo, hi = 0, len(cards)-1
    while lo<=hi:
        mid = (lo + hi) // 2
        if cards[mid] == query:
            if mid-1>=0 and cards[mid-1] == query:
                hi = mid-1
            else:
                return mid
        elif cards[mid] < query:
            hi = mid-1
        elif cards[mid] > query:
            lo = mid+1
    return -1

evaluate_test_cases(locate_card_binary, tests)

TEST CASE #0

Input:
{'cards': [13, 11, 10, 7, 4, 3, 1, 0], 'query': 1}

Expected Output:
6


Actual Output:
6

Execution Time:
0.009 ms

Test Result:
PASSED


TEST CASE #1

Input:
{'cards': [4, 2, 1, -1], 'query': 4}

Expected Output:
0


Actual Output:
0

Execution Time:
0.011 ms

Test Result:
PASSED


TEST CASE #2

Input:
{'cards': [3, -1, -9, -127], 'query': -127}

Expected Output:
3


Actual Output:
3

Execution Time:
0.006 ms

Test Result:
PASSED


TEST CASE #3

Input:
{'cards': [6], 'query': 6}

Expected Output:
0


Actual Output:
0

Execution Time:
0.004 ms

Test Result:
PASSED


TEST CASE #4

Input:
{'cards': [9, 7, 5, 2, -9], 'query': 4}

Expected Output:
-1


Actual Output:
-1

Execution Time:
0.005 ms

Test Result:
PASSED


TEST CASE #5

Input:
{'cards': [], 'query': 7}

Expected Output:
-1


Actual Output:
-1

Execution Time:
0.002 ms

Test Result:
PASSED


TEST CASE #6

Input:
{'cards': [8, 8, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 3}

Expected Output:
7


Actual Output:
7

Execution Time:
0.061 ms

Test Result:
PASSED


TEST CASE #7

Input:
{'cards': [8, 8, 6, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 6}

Expected Output:
2


Actual Output:
2

Execution Time:
0.028 ms

Test Result:
PASSED


SUMMARY

TOTAL: 8, PASSED: 8, FAILED: 0

[(6, True, 0.009),
 (0, True, 0.011),
 (3, True, 0.006),
 (0, True, 0.004),
 (-1, True, 0.005),
 (-1, True, 0.002),
 (7, True, 0.061),
 (2, True, 0.028)]

Time complexity: the final iteration length is 1, which is equal to \((N/2)^k\), and the runtime could be \(ck\), then \(k = log_2N\), and the time complexity is O(\(log_2N\))
Space compleity: O(1)

1.3 General Binary Search

def binary_search(lo, hi, condition): # condition is a function, depends on the question
    """TODO - add docs"""
    while lo <= hi:
        mid = (lo + hi) // 2
        result = condition(mid)
        if result == 'found':
            return mid
        elif result == 'left':
            hi = mid - 1
        else:
            lo = mid + 1
    return -1

# For this question
def locate_card(cards, query):
    def condition(mid):
        if cards[mid] == query:
            if mid-1>=0 and cards[mid-1]==query:
                return "left"
            else:
                return "found"
        elif cards[mid] < query:
            return "left"
        elif cards[mid] > query:
            return "right"
    
    lo, hi = 0, len(cards)-1
    return binary_search(lo, hi, condition)

evaluate_test_cases(locate_card, tests)

TEST CASE #0

Input:
{'cards': [13, 11, 10, 7, 4, 3, 1, 0], 'query': 1}

Expected Output:
6


Actual Output:
6

Execution Time:
0.021 ms

Test Result:
PASSED


TEST CASE #1

Input:
{'cards': [4, 2, 1, -1], 'query': 4}

Expected Output:
0


Actual Output:
0

Execution Time:
0.008 ms

Test Result:
PASSED


TEST CASE #2

Input:
{'cards': [3, -1, -9, -127], 'query': -127}

Expected Output:
3


Actual Output:
3

Execution Time:
0.009 ms

Test Result:
PASSED


TEST CASE #3

Input:
{'cards': [6], 'query': 6}

Expected Output:
0


Actual Output:
0

Execution Time:
0.008 ms

Test Result:
PASSED


TEST CASE #4

Input:
{'cards': [9, 7, 5, 2, -9], 'query': 4}

Expected Output:
-1


Actual Output:
-1

Execution Time:
0.01 ms

Test Result:
PASSED


TEST CASE #5

Input:
{'cards': [], 'query': 7}

Expected Output:
-1


Actual Output:
-1

Execution Time:
0.005 ms

Test Result:
PASSED


TEST CASE #6

Input:
{'cards': [8, 8, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 3}

Expected Output:
7


Actual Output:
7

Execution Time:
0.011 ms

Test Result:
PASSED


TEST CASE #7

Input:
{'cards': [8, 8, 6, 6, 6, 6, 6, 6, 3, 2, 2, 2, 0, 0, 0], 'query': 6}

Expected Output:
2


Actual Output:
2

Execution Time:
0.01 ms

Test Result:
PASSED


SUMMARY

TOTAL: 8, PASSED: 8, FAILED: 0

[(6, True, 0.021),
 (0, True, 0.008),
 (3, True, 0.009),
 (0, True, 0.008),
 (-1, True, 0.01),
 (-1, True, 0.005),
 (7, True, 0.011),
 (2, True, 0.01)]

previous

Data Structure Intro

next

2 Binary Search Trees, Traversals and Balancing