First occurrence of a positive integer using binary search-CodePudding

I've tried to write a code that finds the first occurrence of a positive integer in a sorted array using binary search, but it doesn't work. Here's the code:

def findFirstOccurrence(arr):

    (left, right) = (0, len(arr) - 1)

    result = -1

    while left <= right:
        mid = (left   right) // 2

        if 0 < arr[mid]:
            result = mid
            right = mid - 1
        elif 0 > arr[mid]:
            right = mid - 1
        else:
            left = mid   1
    return result

CodePudding user response：

Below code will help.

def findFirstOccurrence(arr):
  left,right=0,len(arr)-1
  while not((left==right) or (right==left 1)):
    mid=(left right)//2
    if arr[mid]>0:
      right=mid
    else:
      left=mid

  if arr[left]>0:
    return left
  if arr[right]>0:
    return right
  return None

print(findFirstOccurrence([-4,-3,-2,-1,0,1,2,5,3,4,6]))

Output

CodePudding user response：

The error comes from the lines

elif 0 > arr[mid]:
    right = mid - 1

If arr[mid] is negative, we decrease the right pointer — i.e. we look further to the left. But if the array is sorted in ascending order, then anything further to the left of a negative number is still negative, so we'll never reach a positive number and the program will fail.

What we want to do instead is look to the right, where the positive numbers are. The lines

else:
    left = mid   1

already do that in the case that arr[mid] == 0. Removing the two erroneous lines would allow the case that arr[mid] < 0 to fall through and do what we want.

Final code:

if arr[mid] > 0:
    result = mid
    right = mid - 1
else:
    left = mid   1