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:

Solution 1:

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))

defupper(a, val, left, right):

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

Solution 2:

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:
            returnleftelse:
            returnleft-1
    mid = (left+right) //2
    if a[mid] <= val:
        returnupper(a, val, mid+1, right)
    else:
        returnupper(a, val, left, mid)
        

for i inrange(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

Solution 3:

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))

Solution 4:

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:
        returnleft
    mid = (left+right+1) //2

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