First occurrence of 1 in unsorted binary array

Question

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.

There is no reason to use "divide and conquer" technique. Just walk through array insimple loop — MBo
– MBo, Commented Apr 21, 2021 at 8:09
I want to achieve O(log N) complexity with a hypothetical infinite threads in parallel, that's why I'm trying to use divide and conquer for the sequential problem. — space_gladiator
– space_gladiator, Commented Apr 21, 2021 at 8:12

Ogochi · Accepted Answer · 2021-04-21 08:36:29Z

3

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

edited Apr 21, 2021 at 8:36

answered Apr 21, 2021 at 8:28

Ogochi

3303 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

space_gladiator Over a year ago

Thank you for the explanation! I just tested your code on the input [0,0,1,0] and I get an index error in A[start]==1. I don't see why this is the case. Further for cases like first_one([0,0,0,0,1,0,1]), the maximum recursion depth is exceeded.

Ogochi Over a year ago

sorry, didn't test it fully. However idea stays the same ;) fixed!

Collectives™ on Stack Overflow

First occurrence of 1 in unsorted binary array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related