Monday, November 16, 2015

LinkedIn: Binary search greater

Given a sorted array and a target, find the element just greater than the target. If does not exist, return array[0]. 

Understand the problem: 
The problem asks for finding the next element greater to the target. So it suggests a binary search solution. e.g. 
1 2 3 4 5, and target is 3, we return 4. 

There are several corner cases to consider:
1. What if the last element i.e. A[n - 1] is equal or less than the target, then we return A[0]. 
2. What if it contains duplicates. In this case, we cannot just return the next element of the target, e.g. 
1 2 3 3 4, and target = 3. In this case, we will first find the first 3. If we simply returns the next element of 3, it would be errorly 3, not 4. So we might linearly search the rest of the element if it is equal to the target until a greater one, but the algorithm will degrade to a O(n) solution at the worst case. 

Solution:
import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
  public static int searchForGreater(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
      return -1;
    }
    
    int len = nums.length;
    
    if (target >= len) {
      return nums[0];
    }
    
    int lo = 0;
    int hi = len - 1;
    
    while (lo + 1 < hi) {
      int mid = lo + (hi - lo) / 2;
      if (nums[mid] == target) {
        lo = mid + 1;
      } else if (nums[mid] > target) {
        hi = mid;
      } else if (nums[mid] < target) {
        lo = mid + 1;
      }
    }
    
    if (nums[lo] > target) {
      return nums[lo];
    } else if (nums[hi] > target) {
      return nums[hi];
    }
    
    return nums[0];
  }
  
  public static void main(String[] args) {
      int target = 5;
      int n = 6;
      int[] nums = new int[]{1,3,5,5,5,6};
      
      int result = searchForGreater(nums, target);
      System.out.println(result);
      
  }
}

No comments:

Post a Comment