通过在每次成功搜索后加倍来重复搜索元素-yiteyi-C++库

给定一个数组“a[]”和整数“b”。找出a[]中是否存在b。如果存在，则将b的值加倍，然后再次搜索。我们重复这些步骤，直到找不到b为止。最后我们返回b的值。

null

例如：

Input : a[] = {1, 2, 3}          b = 1 Output :4Initially 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

问题来源：在雅特拉被问到。com在线测试

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

1）对输入数组进行排序。 2）继续进行二进制搜索和加倍，直到元素不存在。下面的代码使用 STL中的二进制搜索（）

C++

                         // 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

                         // 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                       
                                                 elif                                     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>                       

输出：

本文由 卡兰·库马尔·戈塔姆 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章