[LintCode] #60 Search Insert Position

attention: if target > all elements in A T_T

public class Solution {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] >= target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if (A[start] >= target) {
            return start;
        } else if (A[end] >= target){
            return end;
        } else {
            return end + 1; // 1st attempt failed: target > all elements in A
        }
    }
}

[LeetCode] #240 Search a 2D Matrix II

1) quadratic search? time complexity O(n)
2) search from bottom left of that 2D array, compare current element with target, exclude one row/column each time O(n + m)

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int i = matrix.length - 1;
        int j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                i--;
            } else {
                j++;
            }
        }
        
        return false;
    }
}

[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;
    }
}