start again - 20200130

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(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                start = mid;
            }else{
                end = mid;
            }
        }
        
        if(nums[start] == target){
            return start;
        }
        
        if (nums[end] == target){
            return end;
        }
        
        return -1;
        
    }
}

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int start = 0;
        int end = A.length -1;
        
        while(start + 1 < end){
            int mid = start + (end -start)/2;
            
            if (mid+1 > A.length-1){
                return -1;
            }

            if (A[mid] < A[mid+1]){
                start = mid;
            }else{
                end = mid;
            }
        }
        
        if (A[start] < A[end]){
            return end;
        }
        
        return start;
    }
}

/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     public int f(int x, int y);
 * };
 */
class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<>();
        
        for (int i = 1; i <= 1000; i++){
            if (customfunction.f(i, 1)>z){
                break;
            }
            
            int start = 1;
            int end = 1000;
            while(start <= end){
                int mid = start + (end - start)/2;
                int temp = customfunction.f(i, mid);
                if(temp == z){
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(mid);
                    res.add(list);
                    break;
                }else if(temp > z){
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }
            }
            
        }
        
        return res;
    }
}

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

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

class Solution {
    public int findMin(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(nums[mid]< nums[nums.length-1]){
                end = mid;
            }
            
            else if (nums[mid] >= nums[nums.length -1]){
                start = mid;
            }
        }
        
        if(nums[start]<nums[end]){
            return nums[start];
        }else{
            return nums[end];
        }
    }
}

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

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