Binary Search

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/binary-search/

题目：
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example: If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

代码：

 class Solution {  
 public:  
   /**  
    * @param nums: The integer array.  
    * @param target: Target number to find.  
    * @return: The first position of target. Position starts from 0.   
    */  
   int binarySearch(vector<int> &array, int target) {  
     // write your code here  
     if (array.empty()) return -1;  
     int start = 0, end = array.size()-1;  
     while (start + 1 < end) {  
       int mid = start + (end-start) / 2;  
       if (array[mid] >= target) {  
         end = mid;  
       } else {  
         start = mid;  
       }  
     }  
     if (array[start] == target) return start;  
     if (array[end] == target) return end;  
     return -1;  
   }  
 };  

162 Find Peak Element

来源：Leetcode

原帖：https://leetcode.com/problems/find-peak-element/

题目：
A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞.

代码：

 class Solution {  
 public:  
   int findPeakElement(const vector<int> &num) {  
     int len = num.size();  
       if (len == 1) return 0;  
       int left = 0, right = len - 1;  
       int mid;  
       while (left + 1 < right) {  
         mid = left + (right - left) / 2;  
         if (num[mid] > num[mid-1] && num[mid] > num[mid+1]) return mid;  
         if (num[mid] < num[mid-1]) right = mid; // like hill climbing   
         else left = mid;  
       }  
       return num[left] > num[right] ? left : right;  
   }  
 };  

Find First Bad Version

来源：Lintcode

原帖：http://www.lintcode.com/en/problem/first-bad-version/

题目：
The code base version is an integer and start from 0 to n. One day, someone commit a bad version in the code case,  so it caused itself and the following versions are all failed in the unit tests. You can determine whether a version is bad by the following interface: boolean isBadVersion(int version);
Find the first bad version.

代码：

 struct TreeNode {  
   int val;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
   
 void find_k_largest_in_BST_helper(TreeNode* root, int k, vector<int> &k_elements) {  
   if (!root || k_element.size() == k) {  
     return;  
   }  
   // Perform reverse inorder traversal  
   if (root && k_elements.size() < k) {  
     find_k_largest_in_BST_helper(root->right, k, k_elements);  
     if (k_elements.size() < k) {  
       k_elements.push_back(root->val);  
       find_k_largest_in_BST_helper(root->left, k, k_elements);  
     }  
   }  
 }  
   
 vector<int> find_k_largest_in_BST(TreeNode* root, int k) {  
   vector<int> k_elements;  
   find_k_largest_in_BST_helper(root, k , k_elements);  
   return k_elements;  
 }  

Search a 2D Matrix I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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]
]
Given target = 3, return true.

代码：

 class Solution {  
 public:  
   //Sort by row first and col next.   
   bool searchMatrix(vector<vector<int> > &matrix, int target) {  
     if (matrix.empty() || matrix[0].empty()) {  
       return false;  
     }  
     int M = matrix.size(), N = matrix[0].size();  
     int start = 0, end = M - 1; // search by row  
     while (start <= end) {  
       int mid = start + (end - start) / 2;  
       if (matrix[mid][0] == target) {  
         return true;  
       } else if (matrix[mid][0] < target) {  
         start = mid + 1;  
       } else {  
         end = mid - 1;  
       }  
     }  
     int row = end; // search by column  
     if (row < 0) {  
       return false;  
     }  
     start = 0, end = N - 1;  
     while (start <= end) { // <=  
       int mid = start + (end - start) / 2;  
       if (matrix[row][mid] == target) {  
         return true;  
       } else if (matrix[row][mid] < target) {  
         start = mid + 1; // mid + 1  
       } else {  
         end = mid - 1; // mid - 1  
       }  
     }  
     return false;  
   }  
 };  
   
 class Solution {  
 public:  
   bool searchMatrix(vector<vector<int> > &matrix, int target) {  
     if (matrix.empty() || matrix[0].empty()) return false;  
     int M = matrix.size(), N = matrix[0].size();  
     int l = 0, h = M*N-1, m;  
     while (l + 1 < h) {  
       m = l + (h - l) / 2;  
       int i = m / N, j=m % N;  
       if (matrix[i][j] == target) return true;  
       else if (matrix[i][j] < target) l = m;  
       else h = m;  
     }  
     return matrix[l/N][l%N] == target || matrix[h/N][h%N] == target ? true : false;  
   }  
 };  

Median of Two Sorted Arrays

来源：Leetcode

原帖：http://oj.leetcode.com/problems/median-of-two-sorted-arrays/

题目：
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Refer details for http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
Solution: Time complexity: O(log(m+n))

代码：

 class Solution {  
 public:  
   //O(log(m+n)), find the k-th sorted array elements  
   double findMedianSortedArrays(int A[], int m, int B[], int n) {  
     int total = m + n;  
     if (total % 2) {  
       return findKthSortedArrays(A, m, 0, B, n, 0, total / 2 + 1); // odd        
     } else {  
       return (findKthSortedArrays(A, m, 0, B, n, 0, total / 2) +   
           findKthSortedArrays(A, m, 0, B, n, 0, total / 2 + 1)) / 2; // even        
     }  
   }  
   
   double findKthSortedArrays(int A[], int m, int A_start, int B[], int n, int B_start, int k) {  
     if (A_start >= m) return B[B_start + k - 1];  
     if (B_start >= n) return A[A_start + k - 1];   
     if (k == 1) return min(A[A_start], B[B_start]);  
   
     int A_key = A_start + k / 2 - 1 < m ? A[A_start + k / 2 - 1] : INT_MAX; // corner case (k/2-1)  
     int B_key = B_start + k / 2 - 1 < n ? B[B_start + k / 2 - 1] : INT_MAX;  
     if (A_key < B_key) {  
       return findKthSortedArrays(A, m, A_start + k / 2, B, n, B_start, k - k / 2);  
     } else {  
       return findKthSortedArrays(A, m, A_start, B, n, B_start + k / 2, k - k / 2);  
     }  
   }  
 };  

First Missing Positive

来源：Leetcode

原帖：http://oj.leetcode.com/problems/first-missing-positive/

题目：
Given an unsorted integer array, find the first missing positive integer.
For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
Solution: Although we can only use constant space, we can still exchange elements within input A.
Swap elements in A and try to make all the elements in A satisfy: A[i] == i + 1. Pick out the first one that does not satisfy A[i] == i + 1.

代码：

 class Solution {  
 public:  
   int firstMissingPositive(int A[], int n) {  
     int i = 0;  
     while (i < n) {  
       if (A[i] != (i + 1) && A[i] >= 1 && A[i] <= n && A[A[i] - 1] != A[i]) {  
         swap(A[i], A[A[i] - 1]);          
       } else {  
         i++;          
       }  
     }  
     for (i = 0; i < n; ++i) {  
       if (A[i] != (i + 1)) {  
         return i + 1;                
       }  
     }  
     return n + 1;  
   }  
 };  

Search Insert Position

来源：Leetcode

原帖：http://oj.leetcode.com/problems/search-insert-position/

题目：
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 -> 2
[1,3,5,6], 2 -> 1
[1,3,5,6], 7 -> 4
[1,3,5,6], 0 -> 0

代码：

 class Solution {  
 public:  
   int searchInsert(int A[], int n, int target) {  
     int start = 0, end = n - 1;  
     while (start + 1 < end) {  
       int mid = start + (end - start) / 2;  
       if (A[mid] == target) {  
         return mid;  
       } else if (A[mid] < target) {  
         start = mid;  
       } else {  
         end = mid;  
       }  
     }  
     if (A[end] == target) {  
       return end;  
     } else if (A[end] < target) {  
       return end + 1;  
     }  
     if (A[start] == target) {  
       return start;  
     } else if (A[start] < target) {  
       return start + 1;  
     }  
     return start;   
   }  
 };  

Search for a Range

来源：Leetcode

原帖：http://oj.leetcode.com/problems/search-for-a-range/

题目：
Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
Solution: It takes O(lgN) to find both the lower-bound and upper-bound.

代码：

 class Solution {  
 public:  
   vector<int> searchRange(int A[], int n, int target) {  
     int start, end, mid;  
     vector<int> bound(2, 0);  
     // search for left bound  
     start = 0; end = n - 1;  
     while (start + 1 < end) {  
       mid = start + (end - start) / 2;  
       if (A[mid] >= target) {  
         end = mid;  
       } else {  
         start = mid;  
       }  
     }  
     if (A[start] == target) {  
       bound[0] = start;  
     } else if (A[end] == target) {  
       bound[0] = end;  
     } else {  
       return {-1, -1};  
     }  
     // search for right bound  
     start = 0; end = n - 1;  
     while (start + 1 < end) {  
       mid = start + (end - start) / 2;  
       if (A[mid] == target) {  
         start = mid;  
       } else if (A[mid] < target) {  
         start = mid;  
       } else {  
         end = mid;  
       }  
     }  
     if (A[end] == target) {  
       bound[1] = end;  
     } else if (A[start] == target) {  
       bound[1] = start;  
     } else {  
       return {-1,-1};  
     }  
     return bound;  
   }  
 };  

Remove Duplicates from Sorted Array II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

题目：
Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3].

代码：

 class Solution {  
 public:  
   int removeDuplicates(int A[], int n) {  
     if (n <= 2) return n;  
     int start = 2; // start point is different with removeDuplicateFromSortedArrayI  
     for (int i = 2; i < n; ++i) {  
       if (A[i] != A[start - 1] || A[i] != A[start - 2]) {  
         A[start++] = A[i];                    
       }  
     }  
     return start;  
   }  
 };  
   

Remove Duplicates from Sorted Array I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/

题目：
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2].

代码：

 class Solution {  
 public:  
   int removeDuplicates(int A[], int n) {  
     int start = 0;  
     for (int i = 0; i < n; ++i) {  
       if (i == 0 || A[i] != A[start - 1]) {  
         A[start++] = A[i];                    
       }  
     }  
     return start;  
   }  
 };  

Remove Element

来源：Leetcode

原帖：http://oj.leetcode.com/problems/remove-element/

题目：
Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length.


代码：

 class Solution {  
 public:  
   int removeElement(int A[], int n, int elem) {  
     int start = 0; // start: position that will be filled  
     for (int i = 0; i < n; ++i) { // i: current position  
       if (A[i] != elem) {  
         A[start++] = A[i];                    
       }  
     }    
     return start;  
   }  
 };  

Sqrt(x)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sqrtx/

题目：
Implement int sqrt(int x). Compute and return the square root of x.

思路：
这道题用binary search搞定。需要注意的是函数签名，在面试中遇到过两种。int sqrt(int); double sqrt(double). 如果输入是int，在进行binary search的时候可能会遇到overflow。 输入是double，需要考虑<1, >1的情况，另外需要考虑double精度问题。

代码：
1] int type input

 class Solution {  
 public:  
     int sqrt(int x) {  
         assert(x >= 0);  
         int l = 0, r = x / 2 + 1;  
         while (l + 1 < r) {  
             // long long mid = l + (r - l) / 2; // overflow problem.   
             // long long sq = mid * mid;  
             // if (sq == x) {  
             //   return mid;  
             // } else if (sq < x) {  
             //   l = mid;  
             // } else {  
             //   r = mid;  
             // }  
   
             int mid = l + (r - l) / 2;  
             int quot = x / mid;  
             if (quot == mid) {  
                 return quot;  
             } else if (quot > mid) {  
                 l = mid;  
             } else {  
                 r = mid;  
             }  
         }  
         if (r * r == x) return r;  
         return l;  
     }  
 };  

2] input is double

 class Solution {  
 public:  
     const double eps = 1.0e-12;  
     // 0 means equal, -1 means smaller, +1 means larger  
     int compare(double a, double b) {  
         if (a == 0) a += eps;  
         if (b == 0) b += eps;  
         double diff = (a - b) / b;  
         return diff > eps ? 1 : diff < -eps ? -1 : 0;  
     };  
   
     double square_root(double x) {  
         // Decide the search range according to x  
         double l, r;  
         if (compare(x, 1.0) < 0) { // x < 1.0  
             l = x; r = 1.0;  
         } else { // x >= 1.0  
             l = 1.0; r = x;  
         }  
         // Keep searching if l < r  
         while (compare(l, r) < 0) {  
             double m = l + 0.5 * (r - l);  
             double square_m = m * m;  
             if (compare(square_m, x) == 0) {  
                 return m;  
             } else if (compare(square_m, x) < 0) {  
                 l = m;  
             } else {  
                 r = m;  
             }  
         }  
         return l;  
     }  
 };