how to fix list range out of index error in this case(binary search)?-CodePudding

I made a function that counts the number of target occurrences using binary search.

But, when I am trying to run this function with the last element in the given list as a target, it gives me the error of 'list index out of range'. Anyone, please help me to solve this issue. Thanks in advance.

def binary_occurences(arr, target):
 
    start = 0
    end = len(arr)-1
    placement = -1
    occurence = 0

    while start <= end:
        center = (start   end)//2
        if target == arr[center]:
          placement = center
          end = center - 1

        elif target < arr[center]:
            end = center - 1
        else:
            start = center   1

    if placement == -1:
      return 'your target element is not in the list'
    else:
      while (arr[placement] == target):
        placement  = 1
        occurence  = 1

    return print("Element", target,"occurs", occurence, "times")
 
arr = [2,5,5,5,6,7,8,8,9,9,9,9,9,10]
target = 10
binary_occurences(arr, target)

IndexError: list index out of range

CodePudding user response：

The issue here is the while loop for counting occurrences will break out of the loop once the arr[placement] does not equal target. When you are searching to see the number of occurrences of the last element of the list, the n 1 element of the list when comparing that to the target will throw an out of bounds error. To compensate for this, add a check prior to seeing whether the arr[placement] == target such that placement is less than the length of arr. Since we are using the logical operator and, it will terminate the loop since the i 1 position is not less than length and we won't check that index.

def binary_occurences(arr, target):
     
    start = 0
    end = len(arr)-1
    placement = -1
    occurence = 0

    while start <= end:
        center = (start   end)//2
        if target == arr[center]:
          placement = center
          end = center - 1

        elif target < arr[center]:
            end = center - 1
        else:
            start = center   1
    if placement == -1:
        return 'your target element is not in the list'
    else:
        while (placement < len(arr) and arr[placement] == target):
            placement  = 1
            occurence  = 1

    return print("Element", target,"occurs", occurence, "times")
 

arr = [2,5,5,5,6,7,8,8,9,9,9,9,9,10]
target = 10
binary_occurences(arr, target)

CodePudding user response：

Consider this implementation. bsearch() will carry out a binary search in an array of ints for the specified value. If found, the index is returned otherwise -1. If we find the value at some offset we then scan both up and down (or left and right if you prefer) counting for any possible additional occurrences:-

def bsearch(nums, x):
    L = 0
    R = len(nums) - 1
    while L <= R:
        m = (L   R) // 2
        v = nums[m]
        if v == x:
            return m
        if v < x:
            L = m   1
        else:
            R = m - 1
    return -1

a = [2,5,5,5,6,7,8,8,9,9,9,9,9,10]

x = 9

if (i := bsearch(a, x)) >= 0:
    c = 1
    for _i in range(i 1, len(a)):
        if a[_i] > x:
            break
        c  = 1
    for _i in range(i-1, 0, -1):
        if a[_i] < x:
            break
        c  = 1
else:
    c = 0
print(f'{x} occurs {c} times')

It goes without saying that the list must be sorted for this to work