Repeatedly search an element by doubling it after every successful search
Given an array “a[]” and integer “b”. Find whether b is present in a[] or not. If present, then double the value of b and search again. We repeat these steps until b is not found. Finally we return value of b.
Examples:
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
Question Source : Asked in Yatra.com Online Test
1) Sort the input array.
2) Keep doing binary search and doubling until the element is not present.
The below code using binary_search() in STL
C++
Java
// 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 |
Python3
# 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#
// 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 // 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 ?> |
Javascript
<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> |
Output:
4
Time Complexity : O(Nlog(N))
Auxiliary Space: O(1)