二分法特性

• 已經(jīng)排好序
• 時間復雜度 logn

做題重要考慮點

1. 初始條件 max=? min=?
2. 最后沒找到，最后的輸出結(jié)果應該是min還是max？
   由于循環(huán)條件（min<=max），若沒有找到的話退出循環(huán)，此時min>max（min等于max+1），要根據(jù)題目要求看要min還是要max。如輸出的是查詢失敗后應該插入的位置：應該是min（右邊位置）。但是若是x的平方根（8的話是2.82842向下取整等于2）就是輸出max（左邊位置）。

35（二分法）搜索插入位置

給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值，并返回其索引。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。

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

• 初始化max = length -1 數(shù)組下標等于位置-1
• 新邊界max = mid -1 或者 min = mid +1
• 循環(huán)控制：min <=max
• 搜索結(jié)束：
  • 找到：輸出位置mid
  • 沒找到的話（min>max）：mid = min 是應該插入的位置

69 x的平方根

實現(xiàn) int sqrt(int x) 函數(shù)。
計算并返回 x 的平方根，其中 x 是非負整數(shù)。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。

• 輸入4得2，輸入8也得2

class Solution {
public:
    int mySqrt(int x) {
        int max = x/2;
        int min = 1;
        int mid = 0;
        if(x==0) return 0;
        if(x==1) return 1;
        while(min<=max)
        {
            mid = (min+max)/2;
            if(mid<x/mid)
            {
                min = mid+1;
            }
            else if(mid>x/mid)
            {
                max = mid-1;
            }
            else
            {
                return mid;
            }
        }
        return max;
    }
};

• 初始條件 r等于x/2就行，min=1
• 注意最后沒找到的話返回的值是max(因為是舍去小數(shù)部分)，而此時max是小于min的，取小的值。
• 注意當x==0跟x==1的特殊情況。

167. 兩數(shù)之和 II - 輸入有序數(shù)組

給定一個已按照升序排列 的有序數(shù)組，找到兩個數(shù)使得它們相加之和等于目標數(shù)。
函數(shù)應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。
思路:兩層循環(huán)，第一層：左邊固定一個x，第二層：后面用二分查找y,找x+y=target。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int min;
        int max;
        int mid;
        for(int i=0;i<numbers.size();i++)
        {
            min = i+1;
            max = numbers.size()-1;
            while(min<=max)
            {
                mid = (max-min)/2+min;
                if(numbers.at(mid)>target-numbers.at(i))
                {
                    max = mid-1;
                }
                else if(numbers.at(mid)<target-numbers.at(i))
                {
                    min = mid+1;
                }
                else
                {
                    return {i+1,mid+1};
                }
            }
        }
        return {};
    }
};

• 加變減是為了防止整數(shù)溢出
  • mid = (max-min)/2+min;
  • if(numbers.at(mid)>target-numbers.at(i))
• 返回值
  • return {1,1}就是返回了一個vector
  • return {} 就是返回了一個空vector

33.搜索旋轉(zhuǎn)排序數(shù)組

假設按照升序排序的數(shù)組在預先未知的某個點上進行了旋轉(zhuǎn)。

( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。

搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回 -1 。

你可以假設數(shù)組中不存在重復的元素。

你的算法時間復雜度必須是 O(log n) 級別。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int max = nums.size()-1;
        int min=0;
        int mid;
        while(min <= max)
        {
            mid = (max - min)/2 + min;
            if(nums[mid] == target)
            {
                return mid;
            }
            else
            {
                if(nums[mid]>=nums[min])
                {//左邊有序
                    if(target>=nums[min]&&target<nums[mid])
                    {//target在有序側(cè)
                        max = mid - 1;
                    }
                    else
                    {//target在有序側(cè)
                        min = mid + 1;
                    }
                }
                else
                {//右邊有序
                    if(target<=nums[max]&&target>nums[mid])
                    {//target在有序側(cè)
                        min = mid + 1;
                    }
                    else
                    {//target在有序側(cè)

                        max = mid - 1;
                    }                    
                }
            }
        }
        return -1;
    }
};

• 思路分兩步
  1. 確定mid左邊有序還是右邊有序
  2. 判斷target是否在有序區(qū)間位置來判斷target是在mid左邊還是右邊

• 二分法：判斷target是在左邊還是右邊

34. 在排序數(shù)組中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標值 target。找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。

你的算法時間復雜度必須是 O(log n) 級別。

如果數(shù)組中不存在目標值，返回 [-1, -1]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int max = nums.size()-1;
        int min = 0;
        int mid;
        int a,b;
        while(min <= max)
        {
            mid = (max - min)/2 + min;
            if(target==nums[mid])
            {
                a = b = mid;
                while(a>=0&&nums[a]==target)
                {
                    a--;
                }
                while(b<=nums.size()-1&&nums[b]==target)
                {
                    b++;
                }
                return {a+1,b-1};

            }
            else if(target < nums[mid])
            {
                max = mid - 1;
            }
            else
            {
                min = mid + 1;
            }
        }
        return {-1,-1};
    }
};

很簡單，按普通二分查找找到位置后，向前向后找邊界即可
注意下標不要越界

74. 搜索二維矩陣

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int min=0;
        int max=matrix.size()-1;
        if(matrix.size()==0 || matrix[0].size()==0) return false;  //避免數(shù)組越界
        while(min<=max)
        {
            int mid = (max-min)/2+min;
            if(matrix[mid][0]==target)
            {
                return true;
            }
            else if(matrix[mid][0]<target)
            {
                min = mid + 1;
            }
            else
            {
                max = mid - 1; 
            }
        }
        if(max==-1) return false;  //避免數(shù)組越界
        int temp = max;
        min = 0;
        max = matrix[temp].size()-1;
        while(min<=max)
        {
            int mid = (max-min)/2+min;
            if(matrix[temp][mid]==target)
            {
                return true;
            }
            else if(matrix[temp][mid]<target)
            {
                min = mid + 1;
            }
            else
            {
                max = mid - 1; 
            }  
        }
        return false;
    }
};

本人方法，較笨，先二分查找，找在哪一個一位數(shù)組中，再在此一位數(shù)組中二分查找
需要多次考慮邊界問題防止數(shù)組越界

class Solution {
  public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    if (m == 0) return false;
    int n = matrix[0].size();

    // 二分查找
    int left = 0, right = m * n - 1;
    int pivotIdx, pivotElement;
    while (left <= right) {
      pivotIdx = (left + right) / 2;
      pivotElement = matrix[pivotIdx / n][pivotIdx % n];
      if (target == pivotElement) return true;
      else {
        if (target < pivotElement) right = pivotIdx - 1;
        else left = pivotIdx + 1;
      }
    }
    return false;
  }
};

leetcode官方題解
核心思想是將二維數(shù)組轉(zhuǎn)化為一維數(shù)組之后用標準的二分查找解決