Poiščite bitonično točko v danem bitoničnem zaporedju
Dobili ste a Bitonic Sequence naloga je najti Bitonic Point v njej. Bitonsko zaporedje je zaporedje števil, ki je prvo strogo povečevanje nato po točki strogo zmanjševanje .
Bitonska točka je točka v bitoničnem zaporedju, pred katero elementi striktno naraščajo in za katero elementi striktno padajo.
Opomba:- Dano zaporedje bo vedno veljavno bitonično zaporedje.
Primeri:
Vnos: arr[] = {8 10 100 200 400 500 3 2 1}
Izhod : 500
Vnos: arr[] = {10 20 30 40 30 20}
Izhod : 40
Vnos : arr[] = {60 70 120 100 80}
Izhod: 120
Kazalo vsebine
- [Naivni pristop] Uporaba linearnega iskanja - O(n) časa in O(1) prostora
- [Pričakovan pristop] Uporaba binarnega iskanja - O(logn) čas in O(1) prostor
[Naivni pristop] Uporaba linearnega iskanja - O(n) časa in O(1) prostora
C++Preprost pristop je iteracija skozi matriko in sledenje maksimum element zgodil doslej. ko je prečkanje končano, vrni največji 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 ));
Izhod
500
[Pričakovan pristop] Uporaba binarnega iskanja - O(logn) čas in O(1) prostor
Vhodna matrika sledi a monotoni vzorec . Če je element manjši kot naslednji leži v i naraščajoči segment matrike in največji element bo zagotovo obstajal za njim. Nasprotno, če je element večji kot naslednji leži v padajoči segment kar pomeni, da je največ na tem položaju ali prej. Zato lahko uporabimo binarno iskanje za učinkovito iskanje največjega elementa v 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 ));
Izhod
500Ustvari kviz
