Encuentre el índice del primer 1 en una array ordenada infinita de 0 y 1

Dada una array ordenada infinita que consta de 0 y 1. El problema es encontrar el índice del primer ‘1’ en esa array. Como la array es infinita, se garantiza que el número ‘1’ estará presente en la array.

Ejemplos:

Input : arr[] = {0, 0, 1, 1, 1, 1} 
Output : 2

Input : arr[] = {1, 1, 1, 1,, 1, 1}
Output : 0

Enfoque: El problema está estrechamente relacionado con el problema de encontrar la posición de un elemento en una array ordenada de números infinitos . Como la array es infinita, no conocemos los límites superior e inferior entre los que tenemos que encontrar la ocurrencia del primer ‘1’. 

A continuación se muestra un algoritmo para encontrar los límites superior e inferior.

Algoritmo: 

posOfFirstOne(arr)
    Declare l = 0, h = 1
    while arr[h] == 0
        l = h
    h = 2*h;
    return indexOfFirstOne(arr, l, h)
}

Aquí h y l son los límites superior e inferior requeridos. indexOfFirstOne(arr, l, h) se usa para encontrar el índice de ocurrencia del primer ‘1’ entre estos dos límites. Consulte esta publicación.

// C++ implementation to find the index of first 1
// in an infinite sorted array of 0's and 1's
#include <bits/stdc++.h>
using namespace std;
 
// function to find the index of first '1'
// binary search technique is applied
int indexOfFirstOne(int arr[], int low, int high)
{
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
 
        // if true, then 'mid' is the index of first '1'
        if (arr[mid] == 1 &&
            (mid == 0 || arr[mid - 1] == 0))
            break;
 
        // first '1' lies to the left of 'mid'
        else if (arr[mid] == 1)
            high = mid - 1;
 
        // first '1' lies to the right of 'mid'
        else
            low = mid + 1;
    }
 
    // required index
    return mid;
}
 
// function to find the index of first 1 in
// an infinite sorted array of 0's and 1's
int posOfFirstOne(int arr[])
{
    // find the upper and lower bounds between
    // which the first '1' would be present
    int l = 0, h = 1;
 
    // as the array is being considered infinite
    // therefore 'h' index will always exist in
    // the array
    while (arr[h] == 0) {
 
        // lower bound
        l = h;
 
        // upper bound
        h = 2 * h;
    }
 
    // required index of first '1'
    return indexOfFirstOne(arr, l, h);
}
 
// Driver program to test above
int main()
{
    int arr[] = { 0, 0, 1, 1, 1, 1 };
    cout << "Index = "
         << posOfFirstOne(arr);
    return 0;
}

// JAVA Code For Find the index of first 1
// in an infinite sorted array of 0s and 1s
import java.util.*;
 
class GFG {
     
    // function to find the index of first '1'
    // binary search technique is applied
    public static int indexOfFirstOne(int arr[],
                                   int low, int high)
    {
        int mid=0;
        while (low <= high) {
            mid = (low + high) / 2;
      
            // if true, then 'mid' is the index of
            // first '1'
            if (arr[mid] == 1 &&
                (mid == 0 || arr[mid - 1] == 0))
                break;
      
            // first '1' lies to the left of 'mid'
            else if (arr[mid] == 1)
                high = mid - 1;
      
            // first '1' lies to the right of 'mid'
            else
                low = mid + 1;
        }
      
        // required index
        return mid;
    }
      
    // function to find the index of first 1 in
    // an infinite sorted array of 0's and 1's
    public static int posOfFirstOne(int arr[])
    {
        // find the upper and lower bounds
        // between which the first '1' would
        // be present
        int l = 0, h = 1;
      
        // as the array is being considered
        // infinite therefore 'h' index will
        // always exist in the array
        while (arr[h] == 0) {
      
            // lower bound
            l = h;
      
            // upper bound
            h = 2 * h;
        }
      
        // required index of first '1'
        return indexOfFirstOne(arr, l, h);
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
 
        int arr[] = { 0, 0, 1, 1, 1, 1 };
        System.out.println("Index = " +
                          posOfFirstOne(arr));
            
    }
}
   
// This code is contributed by Arnav Kr. Mandal.

# Python 3 implementation to find the
# index of first 1 in an infinite
# sorted array of 0's and 1's
 
# function to find the index of first
# '1' binary search technique is applied
def indexOfFirstOne(arr, low, high) :
     
    while (low <= high) :
        mid = (low + high) // 2
  
        # if true, then 'mid' is the index
        # of first '1'
        if (arr[mid] == 1 and (mid == 0 or
                       arr[mid - 1] == 0)) :
            break
  
        # first '1' lies to the left of 'mid'
        elif (arr[mid] == 1) :
            high = mid - 1
  
        # first '1' lies to the right of 'mid'
        else :
            low = mid + 1
     
    # required index
    return mid
     
# function to find the index of first
# 1 in an infinite sorted array of 0's
# and 1's
def posOfFirstOne(arr) :
   
    # find the upper and lower bounds between
    # which the first '1' would be present
    l = 0
    h = 1
  
    # as the array is being considered infinite
    # therefore 'h' index will always exist in
    # the array
    while (arr[h] == 0) :
    
        # lower bound
        l = h
  
        # upper bound
        h = 2 * h
         
    # required index of first '1'
    return indexOfFirstOne(arr, l, h)
     
# Driver program
arr = [ 0, 0, 1, 1, 1, 1 ]
print( "Index = ", posOfFirstOne(arr))
 
# This code is contributed by Nikita Tiwari.

// C# Code For Find the index of first 1
// in an infinite sorted array of 0's and 1's
using System;
 
class GFG {
 
    // function to find the index of first '1'
    // binary search technique is applied
    public static int indexOfFirstOne(int[] arr,
                              int low, int high)
    {
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
 
            // if true, then 'mid' is the index of
            // first '1'
            if (arr[mid] == 1 && (mid == 0 || arr[mid - 1] == 0))
                break;
 
            // first '1' lies to the left of 'mid'
            else if (arr[mid] == 1)
                high = mid - 1;
 
            // first '1' lies to the right of 'mid'
            else
                low = mid + 1;
        }
 
        // required index
        return mid;
    }
 
    // function to find the index of first 1 in
    // an infinite sorted array of 0's and 1's
    public static int posOfFirstOne(int[] arr)
    {
        // find the upper and lower bounds
        // between which the first '1' would
        // be present
        int l = 0, h = 1;
 
        // as the array is being considered
        // infinite therefore 'h' index will
        // always exist in the array
        while (arr[h] == 0) {
 
            // lower bound
            l = h;
 
            // upper bound
            h = 2 * h;
        }
 
        // required index of first '1'
        return indexOfFirstOne(arr, l, h);
    }
 
    /* Driver program to test above function */
    public static void Main()
    {
        int[] arr = { 0, 0, 1, 1, 1, 1 };
        Console.Write("Index = " + posOfFirstOne(arr));
    }
}
 
// This code is contributed by Sam007

<?php
// PHP implementation to find
// the index of first 1 in an
// infinite sorted array of
// 0's and 1's
 
// function to find the index
// of first '1' binary search
// technique is applied
function indexOfFirstOne($arr, $low, $high)
{
    $mid;
    while ($low <= $high)
    {
        $mid = ($low + $high) / 2;
 
        // if true, then 'mid' is
        // the index of first '1'
        if ($arr[$mid] == 1 and
            ($mid == 0 or $arr[$mid - 1] == 0))
            break;
 
        // first '1' lies to
        // the left of 'mid'
        else if ($arr[$mid] == 1)
            $high = $mid - 1;
 
        // first '1' lies to
        // the right of 'mid'
        else
            $low = $mid + 1;
    }
 
    // required index
    return ceil($mid);
}
 
// function to find the index of
// first 1 in an infinite sorted
// array of 0's and 1's
function posOfFirstOne($arr)
{
    // find the upper and lower
    // bounds between which the
    // first '1' would be present
    $l = 0; $h = 1;
 
    // as the array is being considered
    // infinite therefore 'h' index will
    // always exist in the array
    while ($arr[$h] == 0)
    {
 
        // lower bound
        $l = $h;
 
        // upper bound
        $h = 2 * $h;
    }
 
    // required index
    // of first '1'
    return indexOfFirstOne($arr,
                           $l, $h);
}
 
// Driver Code
$arr = array(0, 0, 1, 1, 1, 1);
echo "Index = " ,
      posOfFirstOne($arr);
 
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript implementation to find the index of first 1
// in an infinite sorted array of 0's and 1's
 
// function to find the index of first '1'
// binary search technique is applied
function indexOfFirstOne(arr, low, high)
{
    var mid;
    while (low <= high) {
        mid = parseInt((low + high) / 2);
 
        // if true, then 'mid' is the index of first '1'
        if (arr[mid] == 1 &&
            (mid == 0 || arr[mid - 1] == 0))
            break;
 
        // first '1' lies to the left of 'mid'
        else if (arr[mid] == 1)
            high = mid - 1;
 
        // first '1' lies to the right of 'mid'
        else
            low = mid + 1;
    }
 
    // required index
    return mid;
}
 
// function to find the index of first 1 in
// an infinite sorted array of 0's and 1's
function posOfFirstOne(arr)
{
    // find the upper and lower bounds between
    // which the first '1' would be present
    var l = 0, h = 1;
 
    // as the array is being considered infinite
    // therefore 'h' index will always exist in
    // the array
    while (arr[h] == 0) {
 
        // lower bound
        l = h;
 
        // upper bound
        h = 2 * h;
    }
 
    // required index of first '1'
    return indexOfFirstOne(arr, l, h);
}
 
// Driver program to test above
var arr = [0, 0, 1, 1, 1, 1];
document.write( "Index = "
        + posOfFirstOne(arr));
 
// This code is contributed by rrrtnx.
</script>

Index = 2

Sea p la posición del elemento a buscar. El número de pasos para encontrar el índice alto ‘h’ es O (Log p). El valor de ‘h’ debe ser inferior a 2*p. El número de elementos entre h/2 y h debe ser O(p). Por lo tanto, la complejidad temporal del paso de búsqueda binaria también es O(Log p) y la complejidad temporal general es 2*O(Log p), que es O(Log p).

Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.