Encuentra el punto de transición en una array binaria

Dada una array ordenada que contiene solo los números 0 y 1, la tarea es encontrar el punto de transición de manera eficiente. El punto de transición es el punto donde termina «0» y comienza «1».

Ejemplos: 

Input: 0 0 0 1 1
Output: 3
Explanation: Index of first 1 is 3

Input: 0 0 0 0 1 1 1 1
Output: 4
Explanation: Index of first 1 is 4

Enfoque ingenuo: recorra la array e imprima el índice del primer 1.  

1. Atraviesa la array desde el principio hasta el final de la array.
2. Si el elemento actual es 1, imprima el índice y finalice el programa.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to find
// the transition point
#include<iostream>
using namespace std;
 
// Function to find the transition point
int findTransitionPoint(int arr[], int n)
{
    //perform a linear search and
    // return the index of
    //first 1
    for(int i=0; i<n ;i++)
      if(arr[i]==1)
        return i;
 
    //if no element is 1
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = {0, 0, 0, 0, 1, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int point = findTransitionPoint(arr, n);
 
    point >= 0 ? cout << "Transition point is "
                      << point
        : cout<<"There is no transition point";
    return 0;
}

// Java implementation to find the transition point
import java.util.*;
 
class GFG
{
 
// Function to find the transition point
static int findTransitionPoint(int arr[], int n)
{
    // perform a linear search and return the index of
    // first 1
    for(int i = 0; i < n ; i++)
    if(arr[i] == 1)
        return i;
 
    // if no element is 1
    return -1;
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = {0, 0, 0, 0, 1, 1};
    int n = arr.length;
     
    int point = findTransitionPoint(arr, n);
     
    if (point >= 0)
        System.out.print("Transition point is " + point);
    else
        System.out.print("There is no transition point");
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 implementation to find the transition point
 
# Function to find the transition point
def findTransitionPoint(arr, n):
     
    # perform a linear search and return the index of
    # first 1
    for i in range(n):
        if(arr[i] == 1):
            return i
     
    # if no element is 1
    return -1
 
# Driver code
arr = [0, 0, 0, 0, 1, 1]
n = len(arr)
 
point = findTransitionPoint(arr, n)
 
if point >= 0:
    print("Transition point is", point)
else:
    print("There is no transition point")
     
# This code is contributed by shubhamsingh10

// C# implementation to find the transition point
using System;
 
class GFG
{
 
// Function to find the transition point
static int findTransitionPoint(int []arr ,int n)
{
    // perform a linear search and return the index of
    // first 1
    for(int i = 0; i < n ; i++)
    if(arr[i] == 1)
        return i;
 
    // if no element is 1
    return -1;
}
 
 // Driver method
    public static void Main()
    {
        int []arr = {0, 0, 0, 0, 1, 1};
        int point = findTransitionPoint(arr, arr.Length);
      
        Console.Write(point >= 0 ? "Transition point is " +
                   point : "There is no transition point");
    }
}
  
 
// This code is contributed by shivanisinghss2110

<script>
 
    // Javascript implementation to
    // find the transition point
     
    // Function to find the transition point
    function findTransitionPoint(arr, n)
    {
        // perform a linear search and
        // return the index of
        // first 1
        for(let i = 0; i < n ; i++)
            if(arr[i] == 1)
                return i;
 
        // if no element is 1
        return -1;
    }
     
    let arr = [0, 0, 0, 0, 1, 1];
    let point = findTransitionPoint(arr, arr.length);
 
    document.write(point >= 0 ? "Transition point is " +
                  point : "There is no transition point");
     
</script>

Transition point is 4

Análisis de Complejidad: 

• Complejidad de tiempo: O (n), solo se necesita un recorrido, por lo que la complejidad de tiempo es O (n)
• Espacio Auxiliar: O(1), No se requiere espacio adicional.

Enfoque eficiente: la idea es usar la búsqueda binaria y encontrar el índice más pequeño de 1 en la array. A medida que se ordena la array, se puede realizar una búsqueda binaria.

1. Cree dos variables, l y r , inicialice l = 0 y r = n-1 y una variable ans = -1 para almacenar la respuesta.
2. Repita los pasos a continuación hasta que l <= r , el límite inferior es menor que el límite superior.
3. Compruebe si el elemento en el índice medio mid = (l+r)/2 es uno o no.
4. Si el elemento es uno, busque el índice mínimo de 1 elemento en el lado izquierdo del elemento central, es decir, actualice r = mid – 1 y actualice ans = mid .
5. Si el elemento es cero, busque el índice mínimo de 1 elemento en el lado derecho del elemento central, es decir, actualice l = mid + 1 .

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to find the transition point
#include<iostream>
using namespace std;
 
// Function to find the transition point
int findTransitionPoint(int arr[], int n)
{
    // Initialise lower and upper bounds
    int lb = 0, ub = n-1;
 
    // Perform Binary search
    while (lb <= ub)
    {
        // Find mid
        int mid = (lb+ub)/2;
 
        // update lower_bound if mid contains 0
        if (arr[mid] == 0)
            lb = mid+1;
 
        // If mid contains 1
        else if (arr[mid] == 1)
        {
            // Check if it is the left most 1
            // Return mid, if yes
            if (mid == 0
                    || (mid > 0 &&
                       arr[mid - 1] == 0))
                return mid;
 
            // Else update upper_bound
            ub = mid-1;
        }
    }
    return -1;
}
 
// Driver Code
int main()
{
    int arr[] = {0, 0, 0, 0, 1, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int point = findTransitionPoint(arr, n);
 
    point >= 0 ? cout<<"Transition point is " << point
               : cout<<"There is no transition point";
    return 0;
}

// Java implementation to find the transition point
 
class Test {
    // Method to find the transition point
    static int findTransitionPoint(int arr[], int n)
    {
        // Initialise lower and upper bounds
        int lb = 0, ub = n - 1;
 
        // Perform Binary search
        while (lb <= ub) {
            // Find mid
            int mid = (lb + ub) / 2;
 
            // update lower_bound if mid contains 0
            if (arr[mid] == 0)
                lb = mid + 1;
            // If mid contains 1
            else if (arr[mid] == 1) {
                // Check if it is the left most 1
                // Return mid, if yes
                if (mid == 0
                    || (mid > 0 &&
                       arr[mid - 1] == 0))
                    return mid;
                // Else update upper_bound
                ub = mid - 1;
            }
        }
        return -1;
    }
 
    // Driver method
    public static void main(String args[])
    {
        int arr[] = { 0, 0, 0, 0, 1, 1 };
 
        int point = findTransitionPoint(arr, arr.length);
 
        System.out.println(
            point >= 0 ? "Transition point is " + point
                       : "There is no transition point");
    }
}

# python implementation to find the
# transition point
 
# Function to find the transition
# point
def findTransitionPoint(arr, n):
    # Initialise lower and upper
    # bounds
    lb = 0
    ub = n - 1
 
    # Perform Binary search
    while (lb <= ub):
        # Find mid
        mid = (int)((lb + ub) / 2)
 
        # update lower_bound if
        # mid contains 0
        if (arr[mid] == 0):
            lb = mid + 1
 
        # If mid contains 1
        else if (arr[mid] == 1):
             
            # Check if it is the
            # left most 1 Return
            # mid, if yes
            if (mid == 0 \
                or (mid > 0 and\
                arr[mid - 1] == 0)):
                return mid
 
            # Else update
            # upper_bound
            ub = mid-1
     
    return -1
 
# Driver code
arr = [0, 0, 0, 0, 1, 1]
n = len(arr)
point = findTransitionPoint(arr, n);
if(point >= 0):
    print("Transition point is ", point)
else:
    print("There is no transition point")
 
# This code is contributed by Sam007

// C# implementation to find the transition point
using System;
         
class GFG
{
    // Method to find the transition point
    static int findTransitionPoint(int []arr, int n)
    {
        // Initialise lower and upper bounds
        int lb = 0, ub = n-1;
     
        // Perform Binary search
        while (lb <= ub)
        {
            // Find mid
            int mid = (lb+ub)/2;
     
            // update lower_bound if mid contains 0
            if (arr[mid] == 0)
                lb = mid+1;
     
            // If mid contains 1
            else if (arr[mid] == 1)
            {
                // Check if it is the left most 1
                // Return mid, if yes
                if (mid == 0
                    || (mid > 0 &&
                       arr[mid - 1] == 0))
                    return mid;
     
                // Else update upper_bound
                ub = mid-1;
            }
        }
        return -1;
    }
     
     
    // Driver method
    public static void Main()
    {
        int []arr = {0, 0, 0, 0, 1, 1};
        int point = findTransitionPoint(arr, arr.Length);
     
        Console.Write(point >= 0 ? "Transition point is " +
                   point : "There is no transition point");
    }
}
 
// This code is contributed by Sam007

<?php
// PHP implementation to find
// the transition point
 
// Function to find the
// transition point
function findTransitionPoint($arr, $n)
{
     
    // Initialise lower and
    // upper bounds
    $lb = 0; $ub = $n-1;
 
    // Perform Binary search
    while ($lb <= $ub)
    {
         
        // Find mid
        $mid = floor(($lb + $ub) / 2);
 
        // update lower_bound
        // if mid contains 0
        if ($arr[$mid] == 0)
            $lb = $mid + 1;
 
        // If mid contains 1
        else if ($arr[$mid] == 1)
        {
             
            // Check if it is the
            // left most 1
            // Return mid, if yes
            if ($mid == 0 or
                ($mid > 0 and
                 $arr[$mid - 1] == 0))
                return $mid;
 
            // Else update upper_bound
            $ub = $mid - 1;
        }
    }
    return -1;
}
 
    // Driver Code
    $arr = array(0, 0, 0, 0, 1, 1);
    $n = sizeof($arr);
    $point = findTransitionPoint($arr, $n);
 
    if($point >= 0)
        echo "Transition point is " , $point;
    else
        echo"There is no transition point";
    return 0;
 
// This code is contributed by nitin mittal.
?>

<script>
    // Javascript implementation to find the transition point
     
    // Method to find the transition point
    function findTransitionPoint(arr, n)
    {
        // Initialise lower and upper bounds
        let lb = 0, ub = n-1;
      
        // Perform Binary search
        while (lb <= ub)
        {
            // Find mid
            let mid = parseInt((lb+ub)/2, 10);
      
            // update lower_bound if mid contains 0
            if (arr[mid] == 0)
                lb = mid+1;
      
            // If mid contains 1
            else if (arr[mid] == 1)
            {
                // Check if it is the left most 1
                // Return mid, if yes
                if (mid == 0
                    || (mid > 0 &&
                       arr[mid - 1] == 0))
                    return mid;
      
                // Else update upper_bound
                ub = mid-1;
            }
        }
        return -1;
    }
     
    let arr = [0, 0, 0, 0, 1, 1];
    let point = findTransitionPoint(arr, arr.length);
 
    document.write(point >= 0 ? "Transition point is " +
                  point : "There is no transition point");
       
</script>

Transition point is 4

Análisis de Complejidad: 

• Complejidad de tiempo: O(log n) . La complejidad temporal para la búsqueda binaria es O(log n).
• Espacio Auxiliar: O(1) . No se requiere espacio adicional.

Este artículo es una contribución de Sahil Chhabra . 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.