Binary Search

Question 1

First Bad Version

Answer 1

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
      int left =1;
      int right = n;

  while (left < right){
    int mid = left + (right - left) / 2;
    if (isBadVersion(mid)) right = mid;
    else left = mid + 1;
  }
  if (isBadVersion(left)) return left;
  else return right;
} }

Question 2

Sqrt(x)

Answer 2

public class Solution {
    public int mySqrt(int x) {
      long left = 1;
      long right = x / 2;
      while (left <= right){
        long mid = left + (right - left) / 2;
        long product = mid * mid;
        if (product == x) return (int)mid;
        else if (product < x) left = mid + 1;
        else right = mid - 1;
      }
      if (left * left == x) return (int)left;
      return (int)right;
    }
}

Question 3

Power (x, n)

how to avoid overflow?

Answer 3

class Solution {
    public double myPow(double x, int n) {
        return pow_util(x, n);
    }

public double pow_util(double x, long n) {
    if (n == 0) return 1.0;
    if (n == 1) return x;
    if (n < 0) return pow_util(1/x , -n);
    double result = pow_util(x * x , n/2);
    if (n % 2 == 1)  result *= x;
    return result;
} }

Question 4

Search In a rotated Sorted Array

Answer 4

public class Solution {
    public int search(int[] A, int target) {
      if (A == null || A.length == 0) return -1;
      int left = 0;
      int right = A.length - 1;
       int mid = 0;
      while (left + 1< right){
        mid = left + (right - left) / 2;
        if (A[mid] == target) return mid;
        if (A[left] < A[mid]){
            if (A[left] <= target && target <= A[mid]) right = mid;
            else left  = mid;
        } 
        else {
            if (A[mid] <= target && target <= A[right]) left = mid;
            else right = mid;
        }
      }

  if (A[left] == target) return left;
  if (A[right] == target) return right;  
  return -1;
} }