• API
• FAQ
• Tools
• Archive
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
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.
Top