SHARE
TWEET

Untitled

a guest Feb 17th, 2020 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Lista de inteiros
  2.   Ordenada, crescente
  3.  
  4.   1- Abordagem
  5.     Iterar pelo array e buscar o valor.
  6.  
  7.  
  8.   2- Abordagem
  9.     Descobrir  qual é o pivô  que divide em 2 arrays crescentes (pode ser vazio um dos lados)  
  10.  
  11. */
  12.  . -> |  <- .
  13. [2,5,6,0,0,1,2]
  14.  
  15. . ->       <- .
  16. [0,1,2,2,5,6,0]
  17.  
  18.  
  19. startSecond = 3
  20.  
  21.  
  22.  
  23. 0 1 2 3 4 5 6
  24. L
  25. R
  26. 0,0,1,2,2,5,6
  27.  
  28. 0 ~ startSecond -1
  29. startSecond ~ n-1
  30. R
  31. 2,1,0,0,6,5,2
  32.  
  33.  
  34.  
  35.  
  36.  
  37. {6,2}      
  38.      
  39.                0 1 2 3 4 5 6
  40.                    L R
  41.                     x
  42.                
  43.                                  U > V ->
  44.                                  U > Y , Y + 1, Y + 2 ...
  45.                                  V < X + K, X + K - 1 ...
  46.                                  
  47.               X < X + 1 < X + 2 .. | Y < Y + 1 < Y + 2 ...
  48.                
  49. Input: nums = [2,5,6,0,0,1,2], target = 0
  50. Output: true
  51.  
  52. Input: nums = [2,5,6,0,0,1,2], target = 3
  53. Output: false
  54.  
  55. bool binarySearch(vector<int> &input, int val, int L, int R){
  56.     while(L <= R){
  57.     int mid = (L + R) >> 1;
  58.     if(input[mid] == val) return true;
  59.     if(input[mid] > val){
  60.         R = mid - 1;
  61.     } else{
  62.         L = mid + 1;
  63.     }
  64.   }
  65.   return false;
  66. }
  67.  
  68. bool ok(int guess, int limit){
  69.     return guess <= limit;
  70. }
  71. input = [0,1,1,4]
  72. val = 2
  73.  
  74.  0 1 2 3
  75.      L
  76.      .
  77.    R
  78. [1,4,0,1]
  79.  
  80. [5,6,7,8,0,1,2,3,4]
  81. [4,4,4,4,4,4,4,7,0,4] 4,4,4,4,4,4,4,7
  82.  
  83.  
  84. bool exist(vector<int> &input, val) {
  85.     int L = 0, R = input.size() - 1, startSecond;
  86.   while(L <= R){
  87.     int mid = (L + R) >> 1;
  88.     if( ok(input[mid], input.back() ) ){
  89.         startSecond = mid;
  90.       R = mid - 1;
  91.     } else{
  92.         L = mid + 1;
  93.     }
  94.   }
  95.   return binarySearch(input, val, 0, startSecond -1) || binarySearch(input, val, startSecond, input.size() - 1);
  96. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top