Busque repetidamente un elemento doblándolo después de cada búsqueda exitosa

Dado un arreglo “a[]” y un entero “b”. Encuentra si b está presente en a[] o no. Si está presente, duplique el valor de b y busque de nuevo. Repetimos estos pasos hasta que no se encuentre b. Finalmente devolvemos el valor de b.

Ejemplos: 

Input : a[] = {1, 2, 3}
          b = 1 
Output :4
Initially we start with b = 1. Since 
it is present in array, it becomes 2.
Now 2 is also present in array b becomes 4 .
Since 4 is not present, we return 4.

Input : a[] = {1 3 5 2 12}
          b = 3 
Output :6

Fuente de la pregunta: Preguntado en la prueba en línea de Yatra.com
 

1) Ordenar la array de entrada. 
2) Siga haciendo la búsqueda binaria y duplicando hasta que el elemento no esté presente.
El siguiente código usando binary_search() en STL 

// C++ program to repeatedly search an element by
// doubling it after every successful search
#include <bits/stdc++.h>
using namespace std;
 
int findElement(int a[], int n, int b)
{
    // Sort the given array so that binary search
    // can be applied on it
    sort(a, a + n);
 
    int max = a[n - 1]; // Maximum array element
 
    while (b < max) {
 
        // search for the element b present or
        // not in array
        if (binary_search(a, a + n, b))
            b *= 2;
        else
            return b;
    }
 
    return b;
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    int b = 1;
    cout << findElement(a, n, b);
    return 0;
}

// Java program to repeatedly search an element by
// doubling it after every successful search
import java.util.Arrays;
public class Test4 {
 
    static int findElement(int a[], int n, int b)
    {
        // Sort the given array so that binary search
        // can be applied on it
        Arrays.sort(a);
 
        int max = a[n - 1]; // Maximum array element
 
        while (b < max) {
 
            // search for the element b present or
            // not in array
            if (Arrays.binarySearch(a, b) > -1)
                b *= 2;
            else
                return b;
        }
 
        return b;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3 };
        int n = a.length;
        int b = 1;
        System.out.println(findElement(a, n, b));
    }
}
// This article is contributed by Sumit Ghosh

# Python program to repeatedly search an element by
# doubling it after every successful search
 
def binary_search(a, x, lo = 0, hi = None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid + 1
        else if midval > x:
            hi = mid
        else:
            return mid
    return -1
 
def findElement(a, n, b):
    
    # Sort the given array so that binary search
    # can be applied on it
    a.sort()
  
    mx = a[n - 1] # Maximum array element
  
    while (b < mx):
         
        # search for the element b present or
        # not in array
        if (binary_search(a, b, 0, n) != -1):
            b *= 2
        else:
            return b
    return b
  
# Driver code
a = [ 1, 2, 3 ]
n = len(a)
b = 1
print (findElement(a, n, b))
 
# This code is contributed by Sachin Bisht

// C# program to repeatedly search an
// element by doubling it after every
// successful search
using System;
 
public class GFG {
 
    static int findElement(int[] a,
                           int n, int b)
    {
 
        // Sort the given array so that
        // binary search can be applied
        // on it
        Array.Sort(a);
 
        // Maximum array element
        int max = a[n - 1];
 
        while (b < max) {
 
            // search for the element b
            // present or not in array
            if (Array.BinarySearch(a, b) > -1)
                b *= 2;
            else
                return b;
        }
 
        return b;
    }
 
    // Driver code
    public static void Main()
    {
        int[] a = { 1, 2, 3 };
        int n = a.Length;
        int b = 1;
        Console.WriteLine(findElement(a, n, b));
    }
}
 
// This code is contributed by vt_m.

<?php
// Php program to repeatedly search an element by
// doubling it after every successful search
 
function binary_search($a, $x, $lo=0, $hi=NULL)
{
    if ($hi == NULL)
        $hi = count($a);
    while ($lo < $hi) {
        $mid = ($lo + $hi) / 2;
        $midval = $a[$mid];
        if ($midval < $x)
            $lo = $mid + 1;
        else if ($midval > $x)
            $hi = $mid;
        else
            return $mid;
    }
    return -1;
}
 
function findElement($a, $n, $b)
{
// Sort the given array so that binary search
// can be applied on it
    sort($a);
 
    $mx = $a[$n - 1]; // Maximum array element
 
while ($b < max($a)) {
 
// search for the element b present or
// not in array
    if (binary_search($a, $b, 0, $n) != -1)
        $b *= 2;
    else
        return $b;
}
return $b;
}
 
// Driver code
$a = array(1, 2, 3 );
$n = count($a);
$b = 1;
echo findElement($a, $n, $b);
 
// This code is contributed by Srathore
?>

<script>
 
// JavaScript program to repeatedly search
// an element by doubling it after every
// successful search
function binary_search(a, x, lo = 0, hi = null)
{
    if (hi == null)
        hi = a.length;
         
    while (lo < hi)
    {
        mid = Math.floor((lo + hi) / 2);
        midval = a[mid];
         
        if (midval < x)
            lo = mid + 1;
        else if (midval > x)
            hi = mid;
        else
            return mid;
    }
    return -1;
}
 
function findElement(a, n, b)
{
     
    // Sort the given array so that binary
    // search can be applied on it
    a.sort((a, b) => a - b);
     
    // Maximum array element
    let max = a[n - 1];
 
    while (b < max)
    {
         
        // Search for the element b present or
        // not in array
        if (binary_search(a, a + n, b))
            b *= 2;
        else
            return b;
    }
    return b;
}
 
// Driver code
let a = [ 1, 2, 3 ];
let n = a.length;
let b = 1;
 
document.write(findElement(a, n, b));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción: 

4

Complejidad de tiempo : O(Nlog(N))
Espacio auxiliar : O(1) 

Este artículo es una contribución de Karan Kumar Gautam . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.