在查找算法中，二分查找法是比较高效的查找算法之一，同时二分查找的思路可以应用在很多地方，以下列举一个在Leetcode上的题

Leftmost Column with at Least a One

(This problem is an interactive problem.) A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order. Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1. You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

  • BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed).
  • BinaryMatrix.dimensions() returns a list of 2 elements [rows, cols], which means the matrix is rows * cols.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification. For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

二分查找法的应用 - 图1

Input: mat = [[0,0],[1,1]]

Output: 0

Example 2:

二分查找法的应用 - 图2

Input: mat = [[0,0],[0,1]]

Output: 1

Example 3:

二分查找法的应用 - 图3

Input: mat = [[0,0],[0,0]]

Output: -1

Example 4:

二分查找法的应用 - 图4

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]

Output: 1

Constraints:

  • rows == mat.length
  • cols == mat[i].length
  • 1 <= rows, cols <= 100
  • mat[i][j] is either 0 or 1.
  • mat[i] is sorted in a non-decreasing way.
  1. /**
  2.  * // This is the BinaryMatrix's API interface.
  3.  * // You should not implement it, or speculate about its implementation
  4.  * class BinaryMatrix {
  5.  *   public:
  6.  *     int get(int x, int y);
  7.  *     vector<int> dimensions();
  8.  * };
  9.  */
  11. class Solution {
  12. public:
  13.     int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
  14.         vector<int> dim = binaryMatrix.dimensions();
  16.         int n = dim[0];
  17.         if(n == 0)
  18.             return -1;
  20.         int m = dim[0];
  21.         if(m == 0)
  22.             return -1;
  24.         stack<int>row;
  26.         for(int i = 0; i < n; i++)
  27.         {
  28.             if(binaryMatrix.get(i, m - 1) == 1)
  29.                 row.push(i);
  30.         }
  32.         if(row.empty())
  33.             return -1;
  35.         int hi = m - 1;
  36.         int lo = 0;
  38.         while(row.size() > 1 && lo < hi)
  39.         {
  40.             int mid = (hi + lo) / 2;
  42.             stack<int>tmp;
  43.             stack<int>store = row;
  45.             while(!store.empty())
  46.             {
  47.                 int cur = store.top();
  48.                 store.pop();
  50.                 if(binaryMatrix.get(cur, mid) == 1)
  51.                     tmp.push(cur);
  52.             }
  54.             if(tmp.size() == 0)
  55.                 lo = mid + 1;
  56.             else
  57.             {
  58.                 row = tmp;
  59.                 hi = mid;
  60.             }
  61.         }
  63.         if(row.size() == 1)
  64.         {
  65.             int cur = row.top();
  67.             for(int i = lo; i <= hi; i++)
  68.             {
  69.                 if(binaryMatrix.get(cur, i) == 1)
  70.                     return i;
  71.             }
  72.         }
  74.         if(lo >= hi)
  75.             return lo;
  77.         return -1;
  78.     }
  79. };

题目提供了两种思路，二分查找是最基本的思路

Note1: (Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.


Note2: (Optimal Approach) Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down. If the value at p is 0, move down. If the value at p is 1, move left. Try to figure out the correctness and time complexity of this algorithm.

力扣35 搜索插入位置

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5

输出: 2

示例 2:

输入: [1,3,5,6], 2

输出: 1

示例 3:

输入: [1,3,5,6], 7

输出: 4

示例 4:

输入: [1,3,5,6], 0

输出: 0

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/search-insert-position

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题很明显是二分查找，需要注意的是对于右边界的判断

  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.         int size = nums.size();
  5.         if(size == 0)
  6.             return 0;
  8.         if(nums[0] >= target)
  9.             return 0;
  11.         if(nums[size-1] < target)
  12.             return size;
  14.         int start = 0;
  15.         int end = size - 1;
  17.         while(start < end)
  18.         {
  19.             int mid = start + (end - start)/2;
  20.             if(nums[mid] == target)
  21.                 return mid;
  22.             else if(nums[mid] > target)
  23.                 end = mid;
  24.             else
  25.                 start = mid + 1;
  26.         }
  28.         return start;
  29.     }
  30. };

下面的这种解法是用到了STL

  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.         if (nums.size() == 0)
  5.         {
  6.             nums.push_back(target);
  7.             return 1;
  8.         }
  10.         if(find(nums.begin(), nums.end(), target) == nums.end())
  11.         {
  12.             register int i = 0;
  13.             for (;i < nums.size(); i++)
  14.             {
  15.                 if(nums[i] > target)
  16.                     return i;
  17.             }
  19.             return i;
  20.         }
  21.         else
  22.         {
  23.             for (int i = 0; i < nums.size(); i++)
  24.             {
  25.                 if(nums[i] == target)
  26.                     return i;
  27.             }
  28.         }
  29.     }
  30. };

力扣441 排列硬币

441. 排列硬币

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

n 是一个非负整数，并且在32位有符号整型的范围内。

示例 1:

n = 5

硬币可排列成以下几行:

¤

¤ ¤

¤ ¤

因为第三行不完整，所以返回2.

示例 2:

n = 8

硬币可排列成以下几行:

¤

¤ ¤

¤ ¤ ¤

¤ ¤

因为第四行不完整，所以返回3.

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/arranging-coins

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  1. class Solution {
  2. public:
  3.     int arrangeCoins(int n) {
  4.         long left = 0, right = n;
  5.         long k, curr;
  6.         while(left <= right) 
  7.         {
  8.             k = left + (right - left) / 2;
  9.             curr = k * (k + 1) / 2;
  11.             if(curr == n)
  12.                 return (int)k;
  14.             if(n < curr)
  15.             {
  16.                 right = k - 1;
  17.             }
  18.             else
  19.             {
  20.                 left = k + 1;
  21.             }
  22.         }
  24.         return (int)right;
  25.     }
  26. };

这道题也可以采用数学的方法去做

  1. class Solution:
  2.     def arrangeCoins(self, n: int) -> int:
  3.         return (int)((2 * n + 0.25)**0.5 - 0.5)