Encuentre el máximo entre el recuento de enteros positivos o negativos en la array

Dada una array ordenada arr[] que consta de N enteros, la tarea es encontrar el máximo entre el recuento de enteros positivos o negativos en la array arr[] .

Ejemplos:

Entrada: arr[] = {-9, -7, -4, 1, 5, 8, 9}
Salida: 4
Explicación:
El conteo de números positivos es 4 y el conteo de números negativos es 3. Entonces, el máximo entre 4, 3 es 4. Por lo tanto, imprima 4.

Entrada: arr[] = {-8, -6, 10, 15}
Salida: 2

Enfoque: el problema dado se puede resolver utilizando la búsqueda binaria , la idea es encontrar el primer índice cuyo valor sea positivo y luego imprimir el máximo de idx y (N – idx) como resultado. Siga los pasos a continuación para resolver el problema dado:

• Inicialice dos variables, digamos bajo como 0 y alto como (N – 1) .
• Realice la búsqueda binaria en la array dada arr[] iterando hasta bajo <= alto y siga los pasos a continuación:
  • Encuentre el valor de medio como (bajo + alto) / 2 .
  • Si el valor de arr[mid] es positivo , omita la mitad derecha actualizando el valor de high a (mid – 1) . De lo contrario, omita la mitad izquierda actualizando el valor de bajo a (medio + 1) .
• Después de completar los pasos anteriores, imprima el máximo de bajo y (N – bajo) como resultado.

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

// C++ program for the above approach
 
#include "bits/stdc++.h"
using namespace std;
 
// Function to find the maximum of the
// count of positive or negative elements
int findMaximum(int arr[], int size)
{
 
    // Initialize the pointers
    int i = 0, j = size - 1, mid;
 
    while (i <= j) {
 
        // Find the value of mid
        mid = i + (j - i) / 2;
 
        // If element is negative then
        // ignore the left half
        if (arr[mid] < 0)
            i = mid + 1;
 
        // If element is positive then
        // ignore the right half
        else if (arr[mid] > 0)
            j = mid - 1;
    }
 
    // Return maximum among the count
    // of positive & negative element
    return max(i, size - i);
}
 
// Driver Code
int main()
{
    int arr[] = { -9, -7, -4, 1, 5, 8, 9 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << findMaximum(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
public class GFG {
     
    // Function to find the maximum of the
    // count of positive or negative elements
    static int findMaximum(int arr[], int size)
    {
     
        // Initialize the pointers
        int i = 0, j = size - 1, mid;
     
        while (i <= j) {
     
            // Find the value of mid
            mid = i + (j - i) / 2;
     
            // If element is negative then
            // ignore the left half
            if (arr[mid] < 0)
                i = mid + 1;
     
            // If element is positive then
            // ignore the right half
            else if (arr[mid] > 0)
                j = mid - 1;
        }
     
        // Return maximum among the count
        // of positive & negative element
        return Math.max(i, size - i);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = { -9, -7, -4, 1, 5, 8, 9 };
        int N = arr.length;
     
        System.out.println(findMaximum(arr, N));
 
    }
 
}
 
// This code is contributed by AnkThon

# python program for the above approach
 
# Function to find the maximum of the
# count of positive or negative elements
def findMaximum(arr, size):
 
    # Initialize the pointers
    i = 0
    j = size - 1
 
    while (i <= j):
 
         # Find the value of mid
        mid = i + (j - i) // 2
 
        # If element is negative then
        # ignore the left half
        if (arr[mid] < 0):
            i = mid + 1
 
            # If element is positive then
            # ignore the right half
        elif (arr[mid] > 0):
            j = mid - 1
 
        # Return maximum among the count
        # of positive & negative element
    return max(i, size - i)
 
# Driver Code
if __name__ == "__main__":
 
    arr = [-9, -7, -4, 1, 5, 8, 9]
    N = len(arr)
 
    print(findMaximum(arr, N))
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
 
public class GFG
{
     
    // Function to find the maximum of the
    // count of positive or negative elements
    static int findMaximum(int []arr, int size)
    {
     
        // Initialize the pointers
        int i = 0, j = size - 1, mid;
     
        while (i <= j) {
     
            // Find the value of mid
            mid = i + (j - i) / 2;
     
            // If element is negative then
            // ignore the left half
            if (arr[mid] < 0)
                i = mid + 1;
     
            // If element is positive then
            // ignore the right half
            else if (arr[mid] > 0)
                j = mid - 1;
        }
     
        // Return maximum among the count
        // of positive & negative element
        return Math.Max(i, size - i);
    }
     
    // Driver Code
    public static void Main (string[] args)
    {
        int []arr = { -9, -7, -4, 1, 5, 8, 9 };
        int N = arr.Length;
     
        Console.WriteLine(findMaximum(arr, N));
    }
}
 
// This code is contributed by AnkThon

<script>
// Javascript program for the above approach
 
// Function to find the maximum of the
// count of positive or negative elements
function findMaximum(arr, size)
{
 
  // Initialize the pointers
  let i = 0,
    j = size - 1,
    mid;
 
  while (i <= j)
  {
   
    // Find the value of mid
    mid = i + Math.floor((j - i) / 2);
 
    // If element is negative then
    // ignore the left half
    if (arr[mid] < 0) i = mid + 1;
     
    // If element is positive then
    // ignore the right half
    else if (arr[mid] > 0) j = mid - 1;
  }
 
  // Return maximum among the count
  // of positive & negative element
  return Math.max(i, size - i);
}
 
// Driver Code
let arr = [-9, -7, -4, 1, 5, 8, 9];
let N = arr.length;
 
document.write(findMaximum(arr, N));
 
// This code is contributed by saurabh_jaiswal.
</script>

4

Complejidad temporal : O(log N) Espacio
auxiliar : O(1)