Vind een bitonisch punt in een gegeven bitonische reeks
Je krijgt een Bitonische reeks de taak is om te vinden Bitonisch punt erin. Een bitonische reeks is een reeks getallen die strikt eerst is toenemend dan na een punt strikt afnemend .
Een bitonisch punt is een punt in een bitonische reeks, waarna de elementen strikt toenemen en waarna de elementen strikt afnemen.
Opmerking: - Gegeven reeks zal altijd een geldige bitonische reeks zijn.
Voorbeelden:
Invoer: arr[] = {8 10 100 200 400 500 3 2 1}
Uitvoer : 500
Invoer: arr[] = {10 20 30 40 30 20}
Uitvoer : 40
Invoer : arr[] = {60 70 120 100 80}
Uitgang: 120
Inhoudsopgave
- [Naïeve aanpak] Lineair zoeken gebruiken - O(n) tijd en O(1) ruimte
- [Verwachte aanpak] Binair zoeken gebruiken - O(logn) tijd en O(1) ruimte
[Naïeve aanpak] Lineair zoeken gebruiken - O(n) tijd en O(1) ruimte
C++Een eenvoudige aanpak is om de array te doorlopen en de maximaal element tot nu toe heeft plaatsgevonden. zodra de doortocht voltooid is, retourneert u het maximale element.
// 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 ));
Uitvoer
500
[Verwachte aanpak] Binair zoeken gebruiken - O(logn) tijd en O(1) ruimte
De invoerarray volgt a monotoon patroon . Als een element dat is kleiner dan de volgende ligt het in de i steeds groter wordend segment van de array en het maximale element zal er zeker na bestaan. Omgekeerd als een element dat is groter dan de volgende ligt het in de afnemend segment wat betekent dat het maximum op deze positie of eerder ligt. Daarom kunnen we gebruiken binaire zoekopdracht om efficiënt het maximale element in de array te vinden.
// 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 ));
Uitvoer
500Quiz maken
