Finden Sie den bitonischen Punkt in der gegebenen bitonischen Sequenz
Sie erhalten eine Bitonische Sequenz Die Aufgabe besteht darin, zu finden Bitonischer Punkt darin. Eine bitonische Folge ist eine streng erste Zahlenfolge zunehmend dann nach einem Punkt streng abnehmend .
Ein bitonischer Punkt ist ein Punkt in einer bitonischen Folge, vor dem Elemente streng ansteigend und nach dem Elemente streng abnehmend sind.
Hinweis: – Die gegebene Sequenz ist immer eine gültige bitonische Sequenz.
Beispiele:
Eingang: arr[] = {8 10 100 200 400 500 3 2 1}
Ausgabe : 500
Eingang: arr[] = {10 20 30 40 30 20}
Ausgabe : 40
Eingang : arr[] = {60 70 120 100 80}
Ausgabe: 120
Inhaltsverzeichnis
- [Naiver Ansatz] Verwendung der linearen Suche – O(n)-Zeit und O(1)-Raum
- [Erwarteter Ansatz] Verwendung der binären Suche – O(logn)-Zeit und O(1)-Raum
[Naiver Ansatz] Verwendung der linearen Suche – O(n)-Zeit und O(1)-Raum
C++Ein einfacher Ansatz besteht darin, das Array zu durchlaufen und den Überblick zu behalten maximal Element bisher aufgetreten. Sobald die Durchquerung abgeschlossen ist, wird das maximale Element zurückgegeben.
// 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 ));
Ausgabe
500
[Erwarteter Ansatz] Verwendung der binären Suche – O(logn)-Zeit und O(1)-Raum
Das Eingabearray folgt a monotones Muster . Wenn ein Element ist kleiner als das nächste liegt es im i wachsendes Segment des Arrays und das maximale Element wird definitiv danach existieren. Umgekehrt, wenn ein Element ist größer als das nächste, in dem es liegt abnehmendes Segment Das bedeutet, dass das Maximum entweder an dieser Position oder früher liegt. Deshalb können wir verwenden Binäre Suche um effizient das maximale Element im Array zu finden.
// 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 ));
Ausgabe
500Quiz erstellen
