[LeetCode] #162 Find Peak Element

public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (mid >= 1 && nums[mid - 1] < nums[mid] && mid < nums.length - 2 && nums[mid] > nums[mid + 1] ) {
                return mid;
            } else if (mid >= 1 && nums[mid - 1] < nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        return nums[start] > nums[end] ? start : end;
        
    }
}

[LeetCode] #278 First Bad Version

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 0;
        int end = n;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        return isBadVersion(start) ? start : end;
    }
}

[LeetCode] #74 Search a 2D Matrix

1) search first column of the 2D array, get the last element that is <= target, search the row of that element to find target O(logN) + O(logM)
2) search all the elements in that 2D array 1 time O(log(M*N)) = O(logN) + O(logM) :p

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int start = 0;
        int end = matrix.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        int row = target >= matrix[end][0] ? end : start;

        start = 0;
        end = matrix[0].length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if (target == matrix[row][start] || target == matrix[row][end]) {
            return true;
        }
        
        return false;
    }
}

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0][0] > target || matrix[matrix.length - 1][matrix[0].length - 1] < target) {
            return false;
        }
        
        int start = 0;
        int end = matrix.length * matrix[0].length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            int x = mid / matrix[0].length;
            int y = mid % matrix[0].length;
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] < target) {
                start = mid;
            } else if (matrix[x][y] > target) {
                end = mid;
            }
        }
        if (matrix[end / matrix[0].length][end % matrix[0].length] == target) {
            return true;
        } 
        if (matrix[start / matrix[0].length][start % matrix[0].length] == target) {
            return true;
        } 
        return false;
    }
}

[LeetCode] #81 Search in Rotated Sorted Array II

Do not try to use binary search!!!!! worst case time complexity: O(n)

binarySearch(start, end) {
    if (nums[start] == nums[mid] == nums[end]) { // if always hit this case until the last 1 elem, O(n)
        binarySearch(start, mid);
        binarySearch(mid + 1, end);
    }
}

[LeetCode] #33 Search in Rotated Sorted Array

Need to consider 2 cases for mid => M' and M.
4 cases for target => S<T<M', M'<T, T<M<S, M<T<S

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[mid] >= nums[start]) { // M'
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else { // M
                if (target <= nums[end] && target > nums[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            
        }
        
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        
        return -1;
    }
}

[LintCode] #141 Sqrt(x)

class Solution {
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    public int sqrt(int x) {
        // write your code here
        if (x == 0 || x == 1) {
            return x;
        }
        
        int start = 1;
        int end = x;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int q = x / mid;
            if (q == mid) {
                start = mid;
            } else if (q < mid) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if ( end * end > 0 && end * end <= x ) { // x=2147483647 --> integer overflow T_T
            return end;
        } else {
            return start;
        }
    }
}

T_T 溢出的那个edge case烦死了！擦！

[LintCode] #31 Partition Array

public class Solution {
    /** 
     *@param nums: The integer array you should partition
     *@param k: As description
     *return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
        //write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            while (start < end && nums[start] < k) {
                start++;
            }
            while (start < end && nums[end] >= k) {
                end--;
            }
            
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
        }
        
        if (end == nums.length - 1 && nums[end] < k) { // edge case: all elem in the array < k
            return end + 1;
        } else {
            return start;
        }
    }
}