First occurrence of 1 in unsorted binary array

I am solving a problem to find the first 1 in an unsorted array of 1s and 0s. If any 1 is found program should return the index otherwise return -1. I would like to have divide and conquer solution for this problem, but I am struggling with the base case.

def first_one(A):
  n = len(A)
  leftmost = 0
  if n <= 1:
  # probably would be when n <=1 ? I was returning 0 if A[0] == 1 or n otherwise
  # but this lead to the final result always being determined by the first index. 
    
  idx_left = first_one(A[:int(n/2)])
  idx_right = first_one(A[int(n/2):])
  result = min(idx_left, idx_right)
  if result == n:
    return -1
  else:
    return result

So what should my base case be – to retrieve the actual first index instead of 0 (or -1) all the time? I can’t think of any other base case.

Answer

The problem you have is you don’t remember start of the array in subsequent call. To mitigate this issue you have to keep information about current position in original array. I would either add start index of array to the call result or just pass “position” of subarray with every call.

The base case you proposed at the end of the question should be fine ;) Nest time please say explicitly you want ‘divide and conquer’ solution, because of parallel processing. It would prevent proposals of simpler sequential solutions.

Example solution using divide and conquer:

def first_one(A):
  if len(A) == 0:
    return -1

  return first_one_subarray(A, 0, len(A) - 1)

def first_one_subarray(A, start, end):
  # Incorrect subarray
  if start > end or start > len(A) - 1:
    return -1

  # Check if 1 is on 'first' position
  if A[start] == 1:
    return start
    
  # Divide into two parts
  split_point = max(start + 1, round(end / 2))
  result_left = first_one_subarray(A, start + 1, split_point)
  result_right = first_one_subarray(A, split_point + 1, end)
  
  if result_left != -1:
    return result_left
  else:
    return result_right