二分查找

• 求整数根号Implement int sqrt(int x)

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

• 求两个数组交集Intersection of Two Arrays
  这个问题用Python来解没多大意义，C++的话，先把一个数组排序，然后对另一个数组中的元素，二分查找是否在第一个数组中。

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;
    }
};