class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0:
return 0
left = 1
right = x
while True:
mid = left + (right - left) / 2
if mid > x / mid:
right = mid - 1
elif (mid + 1) > (x / (mid + 1)):
return mid
else:
left = mid + 1
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
set<int> res;
for (size_t i=0; i < nums2.size(); ++i) {
if (binary_search(nums1, nums2[i]))
res.insert(nums2[i]);
}
return vector<int>(res.begin(), res.end());
}
bool binary_search(vector<int>& nums, int a) {
if (0 == nums.size()) return false;
/* 这里注意定义index用int型
* 用size_t的话，假如m=0, r = m - 1会变成一个大的正数，而不是-1，在比较 l <= r 会出问题
*/
int l = 0;
int r = nums.size() - 1;
int m;
while (l <= r) {
m = l + (r - l) / 2;
if (a == nums[m]) return true;
if (a > nums[m])
l = m + 1;
else
r = m - 1;
}
return false;
}
};
