Binary Search and Linear Search

Question 1 

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

cards= [13, 11, 10, 7, 4, 3,8, 9, 24]

query= 24

output = 4

<div><br class="Apple-interchange-newline">def locate_card(cards, query): lo,hi=0,len(cards)-1 while lo<=hi: mid=(lo+hi)//2 mid_number=cards[mid] print("lo",lo,",hi",hi,', mid',mid,',mid_number',mid_number) if mid_number==query: return mid elif mid_number < query: hi=mid - 1 elif mid_number> query: lo=mid+1 return -1</div>

1

def locate_card(cards, query):

2

    lo,hi=0,len(cards)-1

3

    while lo<=hi:

4

        mid=(lo+hi)//2

5

        mid_number=cards[mid]

6

7

        print("lo",lo,",hi",hi,', mid',mid,',mid_number',mid_number)

8

9

        if mid_number==query:

10

            return mid

11

        elif mid_number < query:

12

            hi=mid - 1

13

        elif mid_number> query:

14

            lo=mid+1

15

    return -1

In [61]:

Linear search

<div><br class="Apple-interchange-newline">%%time def locate_card_linear(cards,query): position=0 while position< len(cards): if cards[position]==query: return position position +=1 return -1</div>

1

%%time

2

def locate_card_linear(cards,query):

3

    position=0

4

    while position< len(cards):

5

        if cards[position]==query:

6

            return position

7

        position +=1

8

    return -1

Q 2

how many time the sorted list is rotated:

Linear search

<div><br class="Apple-interchange-newline">def count_rotation_linear(nums): position=0 while position < len(nums): #print(position,nums[position]) if position > 0 and nums[position] < nums[position-1]: return position position +=1 return 0</div>

1

def count_rotation_linear(nums):

2

    position=0

3

    while position < len(nums):

4

        #print(position,nums[position])

5

        if position > 0 and nums[position] < nums[position-1]:

6

            return position

7

        position +=1

8

    return 0

<div><br class="Apple-interchange-newline">def count_rotation_binary(nums): lo=0 hi=len(nums)-1 while lo<=hi: mid=(lo+hi)//2 mid_number=nums[mid] #print(mid,mid_number) if mid > 0 and nums[mid]<nums[mid-1]: return mid elif nums[mid]< nums[hi]: hi=mid-1 else: lo=mid+1 return 0</div>

1

def count_rotation_binary(nums):

2

    lo=0

3

    hi=len(nums)-1

4

    while lo<=hi:

5

        mid=(lo+hi)//2

6

        mid_number=nums[mid]

7

        #print(mid,mid_number)

8

        if mid > 0 and nums[mid]<nums[mid-1]:

9

            return mid

10

        elif nums[mid]< nums[hi]:

11

            hi=mid-1

12

        else:

13

            lo=mid+1

14

    return 0

15

<div><br class="Apple-interchange-newline">#binary search %%time for i in test: result=count_rotation_binary(i['input']['nums']) print(i,'output:',result)</div>

1

#binary search

2

%%time

3

for i in test:

4

    result=count_rotation_binary(i['input']['nums'])

5

    print(i,'output:',result)

{'input': {'nums': [4, 5, 8, 9, 10]}, 'output': 0} output: 0
{'input': {'nums': [4, 5, 6, 7, 8, 1, 2, 3]}, 'output': 5} output: 5
{'input': {'nums': [7, 3, 5]}, 'output': 1} output: 1
{'input': {'nums': [3, 5, 7, 8, 9, 10]}, 'output': 5} output: 0
Wall time: 999 µs

<div><br class="Apple-interchange-newline"># linear search %%time for i in test: result=count_rotation_linear(i['input']['nums']) print(i,'output:',result)</div>

1

# linear search

2

%%time

3

for i in test:

4

    result=count_rotation_linear(i['input']['nums'])

5

    print(i,'output:',result)

{'input': {'nums': [4, 5, 8, 9, 10]}, 'output': 0} output: 0
{'input': {'nums': [4, 5, 6, 7, 8, 1, 2, 3]}, 'output': 5} output: 5
{'input': {'nums': [7, 3, 5]}, 'output': 1} output: 1
{'input': {'nums': [3, 5, 7, 8, 9, 10]}, 'output': 5} output: 0
Wall time: 0 ns