Znajdź punkt bitoniczny w zadanym ciągu bitonicznym
Otrzymałeś A Sekwencja bitoniczna zadaniem jest znaleźć Punkt bitoniczny w tym. Sekwencja bitoniczna to ciąg liczb, który jest ściśle pierwszy wzrastający potem po punkcie ściśle malejące .
Punkt bitoniczny to punkt w sekwencji bitonicznej, przed którym elementy ściśle rosną, a po którym elementy ściśle maleją.
Uwaga: - Podana sekwencja będzie zawsze prawidłową sekwencją bitoniczną.
Przykłady:
Wejście: tablica [] = {8 10 100 200 400 500 3 2 1}
Wyjście : 500
Wejście: tablica [] = {10 20 30 40 30 20}
Wyjście : 40
Wejście : tablica [] = {60 70 120 100 80}
Wyjście: 120
Spis treści
- [Podejście naiwne] Korzystanie z wyszukiwania liniowego - O(n) czasu i O(1) przestrzeni
- [Oczekiwane podejście] Korzystanie z wyszukiwania binarnego - czas O(logn) i spacja O(1).
[Podejście naiwne] Korzystanie z wyszukiwania liniowego - O(n) czasu i O(1) przestrzeni
C++Prostym podejściem jest iteracja po tablicy i śledzenie maksymalny element wystąpił do tej pory. po zakończeniu przejścia zwróć element maksymalny.
// C++ program to find maximum element in bitonic // array using linear search #include #include using namespace std ; int bitonicPoint ( vector < int > & arr ) { int res = arr [ 0 ]; // Traverse the array to find // the maximum element for ( int i = 1 ; i < arr . size (); i ++ ) res = max ( res arr [ i ]); return res ; } int main () { vector < int > arr = { 8 10 100 400 500 3 2 1 }; cout < < bitonicPoint ( arr ); return 0 ; }
C // C program to find maximum element in bitonic // array using linear search #include int bitonicPoint ( int arr [] int n ) { int res = arr [ 0 ]; // Traverse the array to find // the maximum element for ( int i = 1 ; i < n ; i ++ ) res = ( res > arr [ i ]) ? res : arr [ i ]; return res ; } int main () { int arr [] = { 8 10 100 400 500 3 2 1 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( '%d n ' bitonicPoint ( arr n )); return 0 ; }
Java // Java program to find maximum element in bitonic // array using linear search import java.util.Arrays ; class GfG { static int bitonicPoint ( int [] arr ) { int res = arr [ 0 ] ; // Traverse the array to find // the maximum element for ( int i = 1 ; i < arr . length ; i ++ ) res = Math . max ( res arr [ i ] ); return res ; } public static void main ( String [] args ) { int [] arr = { 8 10 100 400 500 3 2 1 }; System . out . println ( bitonicPoint ( arr )); } }
Python # Python program to find maximum element in # bitonic array using linear search def bitonicPoint ( arr ): res = arr [ 0 ] # Traverse the array to find # the maximum element for i in range ( 1 len ( arr )): res = max ( res arr [ i ]) return res if __name__ == '__main__' : arr = [ 8 10 100 400 500 3 2 1 ] print ( bitonicPoint ( arr ))
C# // C# program to find maximum element in bitonic // array using linear search using System ; class GfG { static int bitonicPoint ( int [] arr ) { int res = arr [ 0 ]; // Traverse the array to find // the maximum element for ( int i = 1 ; i < arr . Length ; i ++ ) res = Math . Max ( res arr [ i ]); return res ; } static void Main () { int [] arr = { 8 10 100 400 500 3 2 1 }; Console . WriteLine ( bitonicPoint ( arr )); } }
JavaScript // JavaScript program to find maximum element in // bitonic array using linear search function bitonicPoint ( arr ) { let res = arr [ 0 ]; // Traverse the array to find // the maximum element for ( let i = 1 ; i < arr . length ; i ++ ) res = Math . max ( res arr [ i ]); return res ; } const arr = [ 8 10 100 400 500 3 2 1 ]; console . log ( bitonicPoint ( arr ));
Wyjście
500
[Oczekiwane podejście] Korzystanie z wyszukiwania binarnego - czas O(logn) i spacja O(1).
Tablica wejściowa następuje po a wzór monotoniczny . Jeśli element jest mniejszy niż następny, który leży w i segment rosnący tablicy, a element maksymalny na pewno będzie po niej istniał. I odwrotnie, jeśli element jest większy niż następny, w którym się znajduje segment malejący co oznacza, że maksimum znajduje się albo w tej pozycji, albo wcześniej. Dlatego możemy skorzystać wyszukiwanie binarne aby skutecznie znaleźć maksymalny element w tablicy.
// C++ program to find the maximum element in a bitonic // array using binary search. #include #include using namespace std ; int bitonicPoint ( vector < int > & arr ) { int n = arr . size (); // Search space for binary search. int lo = 0 hi = n - 1 ; int res = n - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // Decreasing segment if ( mid + 1 < n && arr [ mid ] > arr [ mid + 1 ]) { res = mid ; hi = mid - 1 ; } // Increasing segment else { lo = mid + 1 ; } } return arr [ res ]; } int main () { vector < int > arr = { 8 10 100 400 500 3 2 1 }; cout < < bitonicPoint ( arr ); return 0 ; }
C // C program to find the maximum element in a bitonic // array using binary search. #include int bitonicPoint ( int arr [] int n ) { // Search space for binary search. int lo = 0 hi = n - 1 ; int res = hi ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // Decreasing segment if ( mid + 1 < n && arr [ mid ] > arr [ mid + 1 ]) { res = mid ; hi = mid - 1 ; } // Increasing segment else { lo = mid + 1 ; } } return arr [ res ]; } int main () { int arr [] = { 8 10 100 400 500 3 2 1 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( '%d n ' bitonicPoint ( arr n )); return 0 ; }
Java // Java program to find the maximum element in a bitonic // array using binary search. import java.util.Arrays ; class GfG { static int bitonicPoint ( int [] arr ) { int n = arr . length ; // Search space for binary search. int lo = 0 hi = n - 1 ; int res = n - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // Decreasing segment if ( mid + 1 < n && arr [ mid ] > arr [ mid + 1 ] ) { res = mid ; hi = mid - 1 ; } // Increasing segment else { lo = mid + 1 ; } } return arr [ res ] ; } public static void main ( String [] args ) { int [] arr = { 8 10 100 400 500 3 2 1 }; System . out . println ( bitonicPoint ( arr )); } }
Python # Python program to find the maximum element in a bitonic # array using binary search. def bitonicPoint ( arr ): # Search space for binary search. lo = 0 hi = len ( arr ) - 1 res = hi while lo <= hi : mid = ( lo + hi ) // 2 # Decreasing segment if mid + 1 < len ( arr ) and arr [ mid ] > arr [ mid + 1 ]: res = mid hi = mid - 1 # Increasing segment else : lo = mid + 1 return arr [ res ] if __name__ == '__main__' : arr = [ 8 10 100 400 500 3 2 1 ] print ( bitonicPoint ( arr ))
C# // C# program to find the maximum element in a bitonic // array using binary search. using System ; class GfG { static int bitonicPoint ( int [] arr ) { int n = arr . Length ; // Search space for binary search. int lo = 0 hi = n - 1 ; int res = n - 1 ; while ( lo <= hi ) { int mid = ( lo + hi ) / 2 ; // Decreasing segment if ( mid + 1 < n && arr [ mid ] > arr [ mid + 1 ]) { res = mid ; hi = mid - 1 ; } // Increasing segment else { lo = mid + 1 ; } } return arr [ res ]; } static void Main () { int [] arr = { 8 10 100 400 500 3 2 1 }; Console . WriteLine ( bitonicPoint ( arr )); } }
JavaScript // JavaScript program to find the maximum element in a bitonic // array using binary search. function bitonicPoint ( arr ) { const n = arr . length ; // Search space for binary search. let lo = 0 hi = n - 1 ; let res = n - 1 ; while ( lo <= hi ) { let mid = Math . floor (( lo + hi ) / 2 ); // Decreasing segment if ( mid + 1 < n && arr [ mid ] > arr [ mid + 1 ]) { res = mid ; hi = mid - 1 ; } // Increasing segment else { lo = mid + 1 ; } } return arr [ res ]; } const arr = [ 8 10 100 400 500 3 2 1 ]; console . log ( bitonicPoint ( arr ));
Wyjście
500Utwórz quiz
