二分查找

二分查找.png

非递归版本

int binarySearch(const vector<int>& vec, int targetNum)
{
    int lo = 0;
    int hi = vec.size()-1;

    while(lo <= hi) {
        int mid = (hi + lo) / 2;    // mid=lo+(hi-lo)/2 这样写还可以防止溢出
        
        if (vec[mid] == targetNum)
            return mid;
        else if (vec[mid] < targetNum)
            lo = mid + 1;
        else if (vec[mid] > targetNum)
            hi = mid - 1;
    }

    return -1;
    // return lo  lo是该数据应该插入的位置。
}

递归版本

int binarySearch(const vector<int>& vec, int lo, int hi, int targetNum)
{   
    if (lo <= hi)
        return -1;
    
    int mid = (hi + lo)/2;  

    if (vec[mid] < targetNum)
        return binarySearch(vec, mid+1, hi, targetNum);
    else if (vec[mid] > targetNum)
        return binarySearch(vec, lo, mid-1, targetNum);
    else
        return mid;
} 

对二分查找分析

• 在N个有序数组中，进行二分查找最多需要(log2N + 1)次比较(无论是否成功)

  总共有n个元素，渐渐分下去就是n，n/2，n/4，.... n/(2^k)（接下来操作元素的个数），其中k就是循环 的次数，直到n/2^k=1/2，可得k = log2n + 1,（是以2为底，n的对数）所以时间复杂度可以表示O(h)=O(log2n)

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int startIndex = 0;
        int endIndex = nums.size() - 1;
        int midIndex = 0;
        while(startIndex <= endIndex)
        {
            auto midIndex = startIndex + (endIndex - startIndex) / 2;
            if (nums[midIndex] == target)
                return midIndex;
            else if (nums[midIndex] > target)
                endIndex = midIndex - 1;
            else if (nums[midIndex] < target)
                startIndex = midIndex + 1;
        }

        return startIndex;
    }
};

367. 有效的完全平方数

• 暴力
• 二分查找

  class Solution {
  public:
      bool isPerfectSquare(int num) {
          int lo = 1;
          int hi = num;
        
          while(lo <= hi)
          {
              int mid = lo + (hi - lo)/2;  // 可以用>>
              if (mid * mid == num)  // 这里注意溢出
                  return true;
              else if (mid * mid > num)
                  hi = mid - 1;
              else 
                  lo = mid + 1;
          }
        
          return false;
      }
  };
  

• 数学定理
  1 + 3 + 5 + ... + (2n - 1) = n ^ 2

  class Solution {
  public:
      bool isPerfectSquare(int num) {
          int i = 1;
          while(num > 0) {
               num -= i;
               i += 2;
          }
        
          return num == 0;
      }
  };
  

• 牛顿迭代法
  牛顿迭代法参见 https://www.cnblogs.com/qlky/p/7735145.html

  class Solution {
  public:
      bool isPerfectSquare(int num) {
            if (num == 1) {
                return true;
            }
            int i = num / 2;
            while((double)i * i > num) {
                i = (i + num / i) / 2;
            }
            return i * i == num;
      }
  };
  

278. 第一个错误的版本

场景一：isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = 正确版本，B = 错误版本
 |       |       |
left    mid    right

场景二：isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = 正确版本，B = 错误版本
 |       |       |
left    mid    right


bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) 
        {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) 
                right = mid;
            else 
                left = mid + 1;
        }
        
        return left;
    }
};

数组中出现次数超过一半的数字

在排序数组中查找元素的第一个和最后一个位置

• 线性扫描
  从左到右，从右到左
• 二分

  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) 
      {
          int start = findStartIndex(nums, 0, nums.size()-1, target);
          int end = findEndIndex(nums, 0, nums.size()-1, target); 
          return vector<int>{start, end};
      }
    
      int findStartIndex(const vector<int>& nums, int lo, int hi, int target)
      {
          while(lo <= hi)
          {
              int mid = lo + (hi-lo)/2;
              if (nums[mid] == target)
              {
                  if (mid != 0)
                  {
                      if (nums[mid-1] != target)
                          return mid;
                      else
                          hi = mid - 1;
                  }
                  else
                  {
                      return 0;
                  }
              }
              else if (nums[mid] > target)
              {
                  hi = mid - 1;
              }
              else if (nums[mid] < target)
              {
                  lo = mid + 1;
              }
          }
          
          return -1;
      }
    
      int findEndIndex(const vector<int>& nums, int lo, int hi, int target)
      {
          while(lo <= hi)
          {
              int mid = lo + (hi-lo)/2;
              if (nums[mid] == target)
              {
                  if (mid != nums.size()-1)
                  {
                      if (nums[mid+1] != target)
                          return mid;
                      else
                          lo = mid + 1;
                  }
                  else
                  {
                      return nums.size()-1;
                  }
              }
              else if (nums[mid] > target)
              {
                  hi = mid - 1;
              }
              else if (nums[mid] < target)
              {
                  lo = mid + 1;
              }
          }
          
          return -1;
      }
  };
  

50. Pow(x, n)

153. 寻找旋转排序数组中的最小值

• 暴力搜索整个数组，找出最小值
• 二分法