Find index of first one in series/array of zeros and ones where all zeros comes always before all ones. (Java Code )

Search/Find index of first one in series/array  of zeros and ones where all zeros comes always before all ones.

At least one is guaranteed in the series .
Length of array /series is not known .


Example :

Input :
01111111111111111111111111111..... length is not known
output : 1

Input :
00000000000000000000000011111111111.... length is not known
output :  25

Observations :

• Array is sorted .
• You can not use binary search as length is not known .
• Only option remains is sequential scan of zeros till first one is met .whose complexity will be O(n)
• There is zero before one which we are interested .
• Index of one is lowest which we are interested .

How to improve it ?

Lets say take random number or jump size as 10 .
Lets jump by 10 till you get first one . then always move to left with half of jum distance till you get 1 . Which ill be answer.

If we get  ArrayIndexOutOfBoundException then opt for sequential search .

Best  case solution could be  of complexity    (number of jumps  + log2( jump size))  ~ O(n) but better than previous O(n) .

Jump size could  optimized based on data if you have large number of zeros then take jump size large else something like 10 . This is data driven optimization .

This typical case of jump search for array or skip list  search .

There could be two flavors of problem say one with no length known other could be with known length is array .

Solution in java (length is not known )

package com.salpe.arrays;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 /**
  * Jump size is less than array size
  */
 @Test
 public void testSuccess1() {

  int[] arr = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 1 };

  int result1 = search(arr);

  Assert.assertEquals(8, result1);

 }

 /**
  * Jump size is equal to array size
  */
 @Test
 public void testSuccess2() {

  int[] arr = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };

  int result1 = search(arr);

  Assert.assertEquals(10, result1);

 }

 /**
  * Jump size is less than array size
  */
 @Test
 public void testSuccess3() {

  int[] arr = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };

  int result1 = search(arr);

  Assert.assertEquals(17, result1);

 }

 /**
  * Say length of array is not known Complexity is lon2(n)
  * 
  * @param arr
  * @return
  */
 public int search(int... arr) {

  // first decide possible segment
  // Jumping forth and back as per figure till we hit first one .

  // jump size depends on data , optimization is data dependent
  int jump = 10;

  int hi = 0;
  int lo = 0;
  int hiVal = -1;

  while (lo <= hi) {

   try {

    // jump forward
    hi = lo + jump;

    // test for out of index or NaN value
    hiVal  = arr[hi];

   } catch (ArrayIndexOutOfBoundsException arrayIndexOutOfBoundsException) {

    // jump half back
    jump = jump / 2;

    continue;

   }

   if (hiVal == 1) {
    break;
   }

   lo = hi;

  }

  // binary search between segment of possible size segment , segment/2 ,
  // segment/4 and so on
  return searchWithNoRecursion(arr, 1, lo, hi);
 }

 public int searchWithNoRecursion(int[] arr, int value, int lo, int hi) {

  while (lo <= hi) {

   int mid = (lo + hi) / 2;

   if (arr[mid] == value) {

    if (mid == 0) {

     return 0;

    }
    if (arr[mid - 1] == 0) {

     return mid;

    } else {

     hi = mid - 1;
    }

   } else {
    lo = mid + 1;

   }

  }

  // return is case no result found
  return -1;
 }

 public int searchWithRecursion(int[] arr, int value, int lo, int hi) {

  // exit condition
  if (lo > hi) {

   // return special value if term is not found;

   return -1;
  }

  int mid = (lo + hi) / 2;

  if (arr[mid] == value) {

   if (mid == 0) {

    return 0;

   }

   if (arr[mid - 1] == 0) {

    return mid;

   } else {

    return searchWithRecursion(arr, value, lo, mid - 1);

   }

  } else if (value < arr[mid]) {

   return searchWithRecursion(arr, value, lo, mid - 1);

  } else {

   return searchWithRecursion(arr, value, mid + 1, hi);
  }

 }

}

Solution in java (length is  known )

package com.salpe.arrays;

import org.junit.Assert;
import org.junit.Test;

public class BinarySearchUtils {

 @Test
 public void testSuccess1() {

  int[] arr = new int[] { 0, 0, 1, 1, 1 };

  int result1 = searchWithNoRecursion(arr, 1, 0, arr.length - 1);
  int result2 = searchWithRecursion(arr, 1, 0, arr.length - 1);

  Assert.assertEquals(2, result1);
  Assert.assertEquals(2, result2);

 }
 
 @Test
 public void testSuccess2() {

  int[] arr = new int[] { 0, 0, 0, 0, 1 };

  int result1 = searchWithNoRecursion(arr, 1, 0, arr.length - 1);
  int result2 = searchWithRecursion(arr, 1, 0, arr.length - 1);

  Assert.assertEquals(4, result1);
  Assert.assertEquals(4, result2);

 }
 
 @Test
 public void testSuccess3() {

  int[] arr = new int[] { 1, 1, 1, 1, 1 };

  int result1 = searchWithNoRecursion(arr, 1, 0, arr.length - 1);
  int result2 = searchWithRecursion(arr, 1, 0, arr.length - 1);

  Assert.assertEquals(0, result1);
  Assert.assertEquals(0, result2);

 }
 

 public int searchWithNoRecursion(int[] arr, int value, int lo, int hi) {

  while (lo <= hi) {

   int mid = (lo + hi) / 2;

   if (arr[mid] == value) {

    if (mid == 0) {

     return 0;

    }
    if (arr[mid - 1] == 0) {

     return mid;

    } else {

     hi = mid - 1;
    }

   } else {
    lo = mid + 1;

   }

  }

  // return is case no result found
  return -1;
 }

 public int searchWithRecursion(int[] arr, int value, int lo, int hi) {

  // exit condition
  if (lo > hi) {

   // return special value if term is not found;

   return -1;
  }

  int mid = (lo + hi) / 2;

  if (arr[mid] == value) {

   if (mid == 0) {

    return 0;

   }

   if (arr[mid - 1] == 0) {

    return mid;

   } else {

    return searchWithRecursion(arr, value, lo, mid - 1);

   }

  } else if (value < arr[mid]) {

   return searchWithRecursion(arr, value, lo, mid - 1);

  } else {

   return searchWithRecursion(arr, value, mid + 1, hi);
  }

 }

}