CODEWITHSUNDEEP
pythonalgorithmbinary-search
Susha Sushanna
Susha Sushanna

Reputation: 47

function that returns the last met of each numbers in a sorted array

I wrote a function that returns the first met of each numbers from 0 to 9

array = [0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9]


def lower(a, val, left, right):
    if left == right:
        return left
    mid = (left + right) // 2

    if a[mid] < val:
        return lower(a, val, mid+1, right)
    else:
        return lower(a, val, left, mid)

for i in range(10):
    print(lower_bound(array, i , 0, len(array)-1), end =' ')

result: 0 2 4 6 8 10 12 14 16 18 .

I tried to write a function that return the last met of each numbers from 0 to 9. and wanted to get: 1 3 5 7 9 11 13 15 17 19

But it does not works correctly( could you help me to with it? Here is my function.

def upper(a, val, left, right):

    if left == right:
        return left
    mid = (left + right) // 2

    if a[mid] <= val:
        return upper(a, val, mid+1, right)
    else:
        return upper(a, val, left, mid)

Upvotes: 2

Views: 97

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Using the floor function when calculating mid means the function is not symmetrical. You can't just mirror one part of it without considering the other.

def upper(a, val, left, right):
    if left == right:
        return left
    mid = (left + right + 1) // 2

    if a[mid] > val:
        return upper(a, val, left, mid-1)
    else:
        return upper(a, val, mid, right)

Upvotes: 1

GProst
GProst

Reputation: 10227

To find the first met:

for i in range(10):
  print(array.index(i))

To find the last met:

inverted_array = array[::-1]
for i in range(10):
  print(len(array) - 1 - inverted_array.index(i))

Upvotes: 1

Ayoub Omari
Ayoub Omari

Reputation: 906

You need to return left-1 instead of left. This is because when you arrive at the last index of val mid, the first if will look from mid+1 (upper(a, val, mid+1, right))

def upper(a, val, left, right):

    if left == right:
        return left-1
    mid = (left + right) // 2

    if a[mid] <= val:
        return upper(a, val, mid+1, right)
    else:
        return upper(a, val, left, mid)

Upvotes: 1

Yossi Levi
Yossi Levi

Reputation: 1268

The reason is that in every case that you are in the last occurrence and the right is one index after, you find the appropriate index but keep moving one more step. the algorithm seems to be good, but just eliminate this case and everything works fine:

array = [0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9]

def upper(a, val, left, right):

    if left == right:
        if a[left] == val:
            return left
        else:
            return left-1
    mid = (left + right) // 2
    if a[mid] <= val:
        return upper(a, val, mid+1, right)
    else:
        return upper(a, val, left, mid)
        

for i in range(10):
    a = upper(array,i,0,19)
    print(a)

output:

1
3
5
7
9
11
13
15
17
19

checked it for several others and it works fine I think

Upvotes: 1

Related Questions