Pronađite bitonsku točku u zadanom bitonskom nizu
Dobivate a Bitonic Sequence zadatak je pronaći Bitonic Point u njoj. Bitonički niz je niz brojeva koji je prvi striktno povećavajući se zatim nakon točke strogo smanjujući se .
Bitonička točka je točka u bitonskom nizu ispred koje elementi striktno rastu, a nakon koje elementi striktno opadaju.
Napomena:- Dana sekvenca uvijek će biti važeća bitonska sekvenca.
Primjeri:
Ulazni: arr[] = {8 10 100 200 400 500 3 2 1}
Izlaz : 500
Ulazni: arr[] = {10 20 30 40 30 20}
Izlaz : 40
Ulazni : arr[] = {60 70 120 100 80}
Izlaz: 120
Sadržaj
- [Naivni pristup] Korištenje linearnog pretraživanja - O(n) vremena i O(1) prostora
- [Očekivani pristup] Korištenje binarnog pretraživanja - O(logn) vrijeme i O(1) prostor
[Naivni pristup] Korištenje linearnog pretraživanja - O(n) vremena i O(1) prostora
C++Jednostavan pristup je ponavljanje niza i praćenje maksimalno element dogodio do sada. nakon što je obilazak dovršen vrati maksimalni 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 ));
Izlaz
500
[Očekivani pristup] Korištenje binarnog pretraživanja - O(logn) vrijeme i O(1) prostor
Ulazni niz slijedi nakon a monotoni uzorak . Ako je element manji nego sljedeći leži u i rastući segment niza i maksimalni element će sigurno postojati nakon njega. Obrnuto ako je element veća nego sljedeći leži u opadajući segment što znači da je maksimum ili na ovoj poziciji ili ranije. Stoga možemo koristiti binarno pretraživanje za učinkovito pronalaženje maksimalnog elementa u nizu.
// 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 ));
Izlaz
500Napravi kviz
