Binary Search: http://lintcode.com/en/problem/classical-binary-search/

• start + 1 < end 确保三元素 终止的时候只有 start and end 且不重叠
• num[mid] < target => start = mid; 向后拉

public int findPosition(int[] nums, int target) {

    if (nums == null || nums.length == 0) return -1;

    int start = 0;
    int end = nums.length - 1;

    // ensure there are 3 elements, when stop only start and end element left
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) {
            start = mid;
        } else {
            end = mid;
        }    
    }

    // check start and end element
    if (nums[start] == target) return start;
    if (nums[end] == target) return end;

    return -1;
}

Search a 2D matrix: http://www.lintcode.com/en/problem/search-a-2d-matrix/

• 坐标转换 用total表示 x y. matrix[mid/ col][mid % col]. 只用到col
• similar: valid soduku:
  • int x = j/3 + (i/3) * 3;
  • int y = j%3 + (i%3) * 3;

    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int row = matrix.length;
        int col = matrix[0].length;
        int start = 0;
        int end = row * col - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid/col][mid%col] == target) return true;

            if (matrix[mid/col][mid%col] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (matrix[start / col][start % col] == target ||
        matrix[end / col][end % col] == target) {
            return true;
        }

        return false;
    }

Search in Rotated Sorted Array: http://www.lintcode.com/en/problem/search-in-rotated-sorted-array/#

    public int search(int[] A, int target) {

        if (A == null || A.length == 0) {
            return -1;
        }

        int start = 0;
        int end = A.length - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;

            if (A[start] <= A[mid]) {
                if (A[start] <= target && target <= A[mid]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                if (A[mid] <= target && target <= A[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }

        if (A[start] == target) return start;
        if (A[end] == target) return end;

        return -1;
    }

sqrt(x): http://www.lintcode.com/en/problem/sqrtx/

    public int sqrt(int x) {

        // int 不行
        long start = 0;
        long end = x/2 + 1;

        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if (mid * mid <= x) {
                start = mid;
            } else {
                end = mid;
            }
        }

        // 注意 用end
        if (end * end == x) {
            return (int)end;
        }

        return (int)start;
    }

Wood Cut: http://www.lintcode.com/en/problem/wood-cut/#

• want to be: as long as possible, the limitation is k section
• so shrink length with given k
• similar: copy books
  • want as fast as possible, limitation is k copier

    public int woodCut(int[] L, int k) {
        // 在 start end 中找 func(A[], length) = k
        if (L == null || L.length == 0) return 0;

        Arrays.sort(L);
        int start = 1;
        int end = L[L.length - 1];

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;

            // 切得多了 可以长一点
            if (count(L, mid) >= k) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (count(L, start) >= k) return start;
        if (count(L, end) >= k) return end;

        return 0;
    }

    private int count(int[] L, int length) {

        int sum = 0;
        for (int l : L) {
            sum += l / length;
        }

        return sum;
    }

copy books

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        if (pages.length == 0) {
            return 0;  
        }

        int total = 0;
        int max = pages[0];
        for (int i = 0; i < pages.length; i++) {
            total += pages[i];
            if (max < pages[i]) {
                max = pages[i];
            }
        }

        int start = max;
        int end = total;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (countCopiers(pages, mid) > k) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (countCopiers(pages, start) <= k) {
            return start;
        }

        return end;
    }

    private int countCopiers(int[] pages, int limit) {
        if (pages.length == 0) {
            return 0;
        }

        int copiers = 1;
        int sum = pages[0]; // limit is always >= pages[0]
        for (int i = 1; i < pages.length; i++) {
            if (sum + pages[i] > limit) {
                copiers++;
                sum = 0;
            }
            sum += pages[i];
        }

        return copiers;
    }
}

Find Peak Element ii:

class Solution {

    public List<Integer> findPeakII(int[][] A) {
        // this is the nlog(n) method
        int low = 1, high = A.length-2;
        List<Integer> ans = new ArrayList<Integer>();
        while(low <= high) {
            int mid = (low + high) / 2;
            int col = find(mid, A);
            if(A[mid][col] < A[mid - 1][col]) {
                high = mid - 1;
            } else if(A[mid][col] < A[mid + 1][col]) {
                low = mid + 1;
            } else {
                ans.add(mid);
                ans.add(col);
                break;
            }
        }
        return ans;
    }
    int find(int row, int [][]A) {
        int col = 0;
        for(int i = 0; i < A[row].length; i++) {
            if(A[row][i] > A[row][col]) {
                col = i;
            }
        }
        return col;
    } 
}