Binary search

Q1: classic binary search

Given a target integer T and an integer array A sorted in ascending order, find the index i such that A[i] == T or return -1 if there is no such index.

analysis:
binary search is a search algorithm to find a target in a sorted array. find the middle element and compare with the target, if they are equal,find the target in the array, otherwise search the target in left half of the array or right half of the array. Every search kick off half of the elements in the array.
class Solution {
 public:
  int solve(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left <= right) {
      mid = left + (right-left)/2;
      if (input[mid] < target) {
        left = mid+1;
      }else if (input[mid] > target) {
        right = mid-1;
      }else {
        return mid;
      }
    }
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1)

Q2: first occurrence
Given a target integer T and an integer array A sorted in ascending order, find the index of the first occurrence of T in A or return -1 if there is no such index.
analysis:
sorted search problem use binary search to solve. In this problem, if we use the classical binary search algorithm to solve, we will find the middle one of these duplicate elements. So we need to continue searching until find the leftmost one. when the array[mid] is larger or equal to target, we can search left half of the array. when the left and right pointers are neighbors, these two elements are the closest elements to target, but we don't know which one is the answer. we check left first and then right to see if the element is target.]
class Solution {
 public:
  int firstOccur(vector<int> input, int target) {
    // Write your solution here
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] < target) {
        left = mid+1;
      }else if (input[mid] >= target) {
        right = mid;
      }
    }
    //post processing
    if (input[left] == target) return left;
    if (input[right] == target) return right;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1) 

Q3: Last Occurrence
Given a target integer T and an integer array A sorted in ascending order, find the index of the last occurrence of T in A or return -1 if there is no such index.  
analysis:
the same algorithm as the previous problem. the only difference is that when array[mid] is equal to the target, we have to continue searching the right half of the array.

 class Solution {
 public:
  int lastOccur(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] > target) {
        right = mid-1;
      }else {
        left = mid;
      }
    }
    //post processing
    if (input[right] == target) return right;
    if (input[left] == target) return left;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1) 

Q4: closest elements in sorted array
Given a target integer T and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to T. the target may be not in the array.
analysis:
search in sorted array but the target may not in the array. use binary search to find the two most closest elements in the array.In post processing, return the smallest difference of the two elements.
class Solution {
 public:
  int solve(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] < target) left = mid;
      else if (input[mid] > target) right = mid;
      else return mid;
    }
    if (abs(target - input[left]) > abs(target - input[right])) return right;
    else return left;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1)
Q5: K closest in sorted array 

Given a target integer T, a non-negative integer K and an integer array A sorted in ascending order, find the K closest numbers to T in A.
analysis:
if we can use binary search algorithm to find the most closest elements, which is the previous problem, then we can treat that element as a pivot and scan elements in two sides to find the k closest numbers.If Some corner cases have to be consider, if the left pointer reaches 0, then we have to push the right elements to result. The same when the right pointer reaches to the end.
class Solution {
 public:
  vector<int> kClosest(vector<int> array, int target, int k) {
    vector<int> rst;
    //sanity check
    if (array.size() == 0 || k == 0) return rst;
    //find the most closest element
    int left  = 0;
    int right = array.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (array[mid] < target) {
        left = mid;
      }else if (array[mid] > target) {
        right = mid;
      }else break;
    }
    int pivot = 0;
    if (array[mid] == target) pivot = mid;
    else if (abs(array[left] - target) > abs(array[right] - target)) pivot = right;
    else if (abs(array[left] -target) <= abs(array[right] - target)) pivot = left;
    rst.push_back(array[pivot]);
    left = pivot-1;
    right = pivot+1;
    for (int i = 0; i < k-1; i++) {
      while (left >= 0 && right <= array.size()-1) {
        if (abs(array[left] - target) > abs(array[right] - target)) {
          rst.push_back(array[right]);
          right++;
        } else {
          rst.push_back(array[left]);
          left--;
        }
       i++;
       if (i == k-1) return rst;
      }
      if (left >= 0) {
        rst.push_back(array[left--]);
      }
      if (right <= array.size()-1) {
        rst.push_back(array[right++]);
      }
    }
    return rst;
  }
};
time complexity: O(logn) + O(k) = O(logn)
space complexity: O(1)

Q6: total occurance
Given a target integer T and an integer array A sorted in ascending order, Find the total number of occurrences of T in A.  
analysis:
search in sorted array use binary search algorithm. we can find the first occurrence of the target in the array then find the last occurrence of the target in the array and return the difference + 1;
class Solution {
 public:
  int totalOccurrence(vector<int> input, int target) {
    // Write your solution here
    //sanity check
    if (input.size() == 0) return 0;
    //find the first occurance of the target
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] >=target) {
        right = mid;
      }else left = mid+1;
    }
    int pivot = 0;
    if (input[left] == target) pivot = left;
    else if (input[right] == target) pivot = right;
    else return 0;
    //find the last occurrence of the target
    left = 0;
    right  = input.size()-1;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] <= target) left = mid;
      else right = mid-1;
    }
    if (input[right] == target) return right - pivot+1;
    if (input[left] == target) return left - pivot +1;
    return 0;
  };
time complexity: O(logn) + O(logn) = O(logn)
space complexity: O(1)

Q7:shift position
Given an integer array A, A is sorted in ascending order first then shifted by an arbitrary number of positions, For Example, A = {3, 4, 5, 1, 2} (shifted left by 2 positions). Find the index of the smallest number.There are no duplicate elements in the array.
analysis:
For shifted sorted array(without duplicate elements in the array), the important property is the whole array can be treated as two parts in ascending order. Think this scenario in two extremely cases: only one element shifted and only one element isn't shifted. These two cases can be detected by comparing the middle element and the rightmost element. if mid < right, it means elements from mid to right are in ascending order, which is case one.Then we can continue searching the smallest element in the left part of the middle element. if mid > right, it means elements from left to mid are in ascending order, which is case two. Then we can continue searching the smallest element in the right part of the middle element.
 class Solution {
 public:
  int shiftPosition(vector<int> input) {
    // Write your solution here
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right - left)/2;
      if (input[mid] < input[right]) { //mid-right is in ascending order
        right = mid;
      }else if (input[mid] > input[right]) { //left-mid is in ascending order
        left = mid+1;
      }
    }
    if (input[left] < input[right]) return left;
    else return right;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1)

Q8:search in shifted array(without duplicates)
Given a target integer T and an integer array A, A is sorted in ascending order first, then shifted by an arbitrary number of positions.
analysis:
This is an extension of the previous problem. For each case, case 1: mid -> right is in ascending order, the target can only be in two parts, one is between mid and right, the other is smaller than mid; case 2: left->mid is in ascending order, the target can only be in two parts, one is between left and mid and the other is larger than mid. One corner case is that if the mid , left  and right are in the same position, then each case is allowed.
class Solution {
 public:
  int search(vector<int> input, int target) {
    // Write your solution here
    //sanitary check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left <= right) {
      mid = left + (right - left) / 2;
      if (input[mid] == target) return mid;
      if (input[mid] <= input[right]) { //mid-right ascending order
        if (input[mid] < target && input[right] >= target) {
          left = mid + 1;
        }else right = mid - 1;
      }else{
        if (input[mid] > target && input[left] <= target) {
          right = mid - 1;
        }else left = mid + 1;
      }
    }
    return -1;
  }
};
time complexity: O(log(n))
space complexity: O(1)
Q9: Search In Shifted Sorted Array II
Given a target integer T and an integer array A, A is sorted in ascending order first, then shifted by an arbitrary number of positions.
analysis:
extension from previous problem, duplicates are allowed. If duplicates exists, three cases should be considered,which is different from the previous one. case 1: mid->right is in ascending order; case 2: left->mid is in ascending order; case 3: input[mid] == input[right], for case 3, do right--, change the position of mid to make it not equal to input[right].
class Solution {
 public:
  int solve(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left <= right) {
      mid = left + (right-left)/2;
      if (input[mid] == target) return mid;
      if (input[mid] < input[right]) {
        if (input[mid] < target && input[right] >= target) {
          left = mid+1;
        }else {
          right  = mid-1;
        }
      } else if (input[mid] > input[right]) {
        if (input[mid] > target && input[left] <= target) {
          right = mid-1;
        }else {
          left = mid+1;
        }
      }else {
        right--;
      }
    }
    return -1;
  }
};
time complexity : O(n) 
in worst case, right-- cause the time complexity changing from O(logn) to O(n)
space complexity: O(1)