首页 > 代码库 > LeetCode算法编程之连载四（二分法）
LeetCode算法编程之连载四（二分法）
1、题目 – Sqrt(x)
Implement int sqrt(int x).Compute and return the square root of x.
题目意思很简单，就是求出x的平方根。
分析：
一看这题目，感觉很简单，很容易想到的是二分法，我最开始的解法是从1、2、4、8 … 2 * n，计算出n < x < 2n，然后再在 n 和 2n间，用二分法，找到平方根结果。
这种方法比较麻烦的一点是，乘积是有可能越界的，要处理乘积越界的情况，代码可读性不强。
class Solution {public: int sqrt(int x) { int base = 1; int product = base * base; while (product < 0 || (product > 0 && product < x)) { base *= 2; product = base * base; } if (product == x) { return base; } int start = base / 2; int end = base; int med = start + (end - start) / 2; while (start != med) { int product = med * med; if ((product >= 0 && product > x) || product < 0) { end = med; } else { start = med; } med = start + (end - start) / 2; } return med; }};
要解决乘积越界的情况，有没有什么好的办法呢？能不能思考一下，在32位可表达的情况下，平方根可能出现的最大的情况？想到位图是不是可以来表示呢？利用二分法，
（1 << 16）的平方为1 << 32位（这已越界），那么最大值是1 << 15，既然知道可表示的最大位数是15，那么依次往低走，根据乘积与x的比较看看每一位可否置1，根据这个思路，有了位图的解决方法：
class Solution {public: int sqrt(int x) { unsigned int res = 0; int bit = 1 << 15; while (bit > 0) { res |= bit; if (res * res > x) { res ^= bit; } bit >>= 1; } return res; }};
这个代码是不是很漂亮了？
2、题目 - Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.For example,Consider the following matrix:[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
题目解释：
输入为一个m x n的矩阵，矩阵每行已从小到大排序，每行第一个数大上一行的最后一个数，在矩阵中是否能找到数x。
分析：
很容易想到，先到这个数所在行，然后在找到这个数所在的列。当然依次遍历过去的是可以的，反正是已经排过序的，这是最笨的方法。但作为搞算法的，最基本的方法就是二分法，
思路是一样的，利用行二分法，找到所在行，再利用列二分法，找到所在的列。
class Solution {public: bool searchMatrix(vector<vector<int> > &matrix, int target) { int row = matrix.size(); if (row == 0) { return false; } int col = matrix[0].size(); int start = 0; int end = row - 1; int med = start + (end - start) / 2; // 二分法找行 while (med != start) { if (matrix[med][0] == target) { return true; } if (matrix[med][0] > target) { end = med; } else { start = med; } med = start + (end - start) / 2; } int exact_row = end; if (matrix[end][0] > target) { exact_row = start; } start = 0; end = col - 1; med = start + (end - start) / 2; // 二分法找列 while (start != med) { if (matrix[exact_row][med] == target) { return true; } if (matrix[exact_row][med] > target) { end = med; } else { start = med; } med = start + (end - start) / 2; } if (matrix[exact_row][start] == target || matrix[exact_row][end] == target) { return true; } return false; }};
LeetCode算法编程之连载四（二分法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。