Binary Search - How to Succeed in Algorithms Interview


Binary Search - How to Succeed in Algorithms Interview
Application

Types

  1. Compare left, right, mid
  2. compare mid, mid-1, mid+1
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
    int lo = 0, hi = arr.size() - k;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (x - arr.get(mid) > arr.get(mid+k) - x)
            lo = mid + 1;
        else
            hi = mid;
    }
    return arr.subList(lo, lo + k);
}
  • TreeSet, TreeMap
int ret = Arrays.binarySearch(arr, value);
if(ret < 0) ret = -ret - 1

Implementation - Different

  • Mistakes: deadlock,
  • invariants
  • Prefer []
  • int mid = left + (right - left) / 2; then left=mid+1
  • or mid = low + ((high - low + 1) / 2); then left=mid ### Possible Bugs | | | | | |-|-|-|-| low|high|mid|while(?) mid + 1 | mid - 1|low + ((high - low) / 2)|low <= high mid + 1 | mid |low + ((high - low) / 2) | low < high mid | mid - 1 | low + ((high - low + 1) / 2) | low < high mid | mid | X(infinite loop) | X(invalid)
  • loop not exit
  • test with cases: left=2, right=3; mid=2
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                 int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}
public int searchRightIndex(int[] nums, int left, int right, int target) {  
    while (left <= right) {  
        int mid = (left + right) / 2;  
        if (nums[mid] > target) right = mid - 1;  
        else left = mid + 1;  
    }  
    return right;  
}  
public int searchLeftIndex(int[] nums, int left, int right, int target) {  
    while (left <= right) {  
        int mid = (left + right) / 2;  
        if (nums[mid] < target) left = mid + 1;  
        else right = mid - 1;  
    }  
    return left;  
}  
public int mySqrt(int x) {
    long l=0,r=x; //in case of overflow
    while(l<r){
        long mid=l+(r-l+1)/2;
        if(mid*mid>x) r=mid-1;
        else l=mid;
    }
    return (int)l;
}
int mySqrt(int x) {
    if (x <= 1) return x;
    int left = 0, right = x;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (x / mid >= mid) left = mid + 1;
        else right = mid;
    }
    return right - 1;
}
int maxElementLesser(int[] array, int key) {
  int length = array.length;
  int low = 0;
  int high = length - 1;
  while (low < high) {
    int mid = low + ((high - low + 1) / 2);//\\
    int current = array[mid];
    if (current == key) {
      return array[mid];
    } else if (current < key) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  return array[low];
}

Search in rotated sort array

public int search(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    while (start <= end) {
        int mid = ( start + end) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[start] <= nums[mid]) {
            if (nums[start] <= target && target < nums[mid]) {
                end = mid -1;
            }
            else {
                start = mid + 1;
            }
        }
        else{
            if (nums[mid] < target && target <= nums[end]) {
                start = mid + 1;
            }
            else {
                end = mid -1;
            }
        }
    }
    return -1;
}
  • LeetCode 81 - Search in Rotated Sorted Array II
  • LeetCode 154 - Find Minimum in Rotated Sorted Array II

Examples

int findPeakElement(const vector<int> &num)
{
    int low = 0;
    int high = num.size()-1;
    while(low < high)
    {
        int mid1 = low + (high-low)/2;
        int mid2 = mid1+1;
        if(num[mid1] < num[mid2])
            low = mid2;
        else
            high = mid1;
    }
    return low;
}

Duplicates

int magicHelper(int arr[],int n,int l,int r)
{
    if(l>r||l<0||r>=n)
        return -1;
    int mid=(l+r)/2;
    if(mid==arr[mid])
        return mid;
    int rightindex=min(mid-1,arr[mid]);
    int left=magicHelper(arr,n,l,rightindex);
    if(left>=0)
        return left;
    int leftindex=max(mid+1,arr[mid]);
    int right=magicHelper(arr,n,leftindex,r);
    return right;
}
int magicFast(int arr[],int n)
{
    if(n==0)
        return -1;
    return magicHelper(arr,n,0,n-1);
}
  • [Smallest Rectangle Enclosing Black Pixels]
public int minArea(char[][] image, int x, int y) {
 int m = image.length, n = image[0].length;
 int colMin = binarySearch(image, true, 0, y, 0, m, true);
 int colMax = binarySearch(image, true, y + 1, n, 0, m, false);
 int rowMin = binarySearch(image, false, 0, x, colMin, colMax, true);
 int rowMax = binarySearch(image, false, x + 1, m, colMin, colMax, false);
 return (rowMax - rowMin) * (colMax - colMin);
}

public int binarySearch(char[][] image, boolean horizontal, int lower, int upper, int min, int max, boolean goLower) {
 while(lower < upper) {
  int mid = lower + (upper - lower) / 2;
  boolean inside = false;
     for(int i = min; i < max; i++) {
      if((horizontal ? image[i][mid] : image[mid][i]) == '1') {
       inside = true;
       break;
      }
     }
  if(inside == goLower) {
   upper = mid;
  } else {
   lower = mid + 1;
  }
 }
 return lower;
}

Resources

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)