logo

TechCodeview

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

Preprost pristop je iteracija skozi matriko in sledenje maksimum element zgodil doslej. ko je prečkanje končano, vrni največji element.

C++ 
// 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('%dn' 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++ 
// 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('%dn' 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 
500
Ustvari kviz