// Find the index of first 1 in a sorted array of 0’s and 1’s

/**
 * Given a sorted array consisting 0’s and 1’s. The problem is to find the index of first ‘1’ in the sorted array.
 * It could be possible that the array consists of only 0’s or only 1’s. If 1’s are not present in the array then print “-1”.
 *
 * Examples:
 *    Input : arr[] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 1}
 *    Output : 6
 *    Explanation: The index of first 1 in the array is 6.

 *    Input : arr[] = {0, 0, 0, 0}
 *    Output : -1
 *    Explanation: 1’s are not present in the array.
 *
 * Source: Asked in Amazon Interview
 */

#include <iostream>
#include <chrono>

int firstIdxOfFirstOne(int *arr, int n);
int firstIdxOfFirstOne2(int *arr, int n);

int main()
{
   int arr[1000000]{};
   arr[999999] = 1;

   int n = sizeof(arr) / sizeof(*arr);
   auto start = std::chrono::steady_clock::now();
   printf("%d\n", firstIdxOfFirstOne(arr, n));
   // printf("%d\n", firstIdxOfFirstOne2(arr, n));
   auto end = std::chrono::steady_clock::now();
   auto totalDuration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
   std::cout << "Operation took: " << totalDuration << " miliseconds\n";
}

int firstIdxOfFirstOne(int *arr, int n)
{
   if (arr[0] == 1)
      return 0;

   int i = 1;
   for (; i < n && arr[i] == 0; i *= 2)
   {
   }

   int left = (i / 2) + 1;
   int right = i >= n ? n - 1 : i;
   int middle = -1;
   while (left <= right)
   {
      middle = (right - left) / 2 + left;
      if (arr[middle] == 1 && arr[middle - 1] == 0)
         return middle;
      else if (arr[middle] == 0)
         left = middle + 1;
      else
         right = middle - 1;
   }
   return -1;
}

int firstIdxOfFirstOne2(int *arr, int n)
{
   if (arr[0] == 1)
      return 0;

   int left = 0;
   int right = n - 1;
   int middle = -1;

   while (left <= right)
   {
      middle = (right - left) / 2 + left;
      if (arr[middle] == 1 && arr[middle - 1] == 0)
         return middle;
      else if (arr[middle] == 0)
         left = middle + 1;
      else
         right = middle - 1;
   }
   return -1;
}

/*
if (arr[0] == 1)
      return 0;

   int left, right, mid;
   left = 0, right = n - 1;
   while (left <= right)
   {
      mid = (right - left) / 2 + left;

      if (arr[mid] == 1 && arr[mid - 1] == 0)
         return mid;
      else if (arr[mid] == 0)
         left = mid + 1;
      else
         right = mid - 1;
   }
   return -1;

*/