Find the Index from which 0 starts

by

Objec­tive:  Given an array of integer which 1’s followed by 0’s. Find the starting index of 0.

Example:

int [] a = {1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0};
First Index from where 0 starts: 10

int [] a = {1,1,1};  //No 0 is present
output: Array does not have 0

int [] a = {0,0,0};  //Only 0’s. return the first index
output: 0

Similar Problem: Find the increasing OR decreasing point in an array

Approach 1: Linear Search:

Navigate the array and look for first occurrence of 0.

  • Handle the edge cases.
  • Time Complexity: O(n)

Code:


Approach 2: Binary Search

  • Modify the binary search.
  • If mid element is 0 and left neighbor is 1, return the mid index
  • If mid element is 0 and left neighbor is 0, Do a recursive call on the left half of the array (start, mid).
  • If mid element is 1, Do a recursive call on the right half of the array (mid+1, end).
  • Handle the base cases (see the code).

Time Complexity: O(logn)

Code:


Output:

(Binary Search)First Index from where 0 starts: 21

Related Posts: