Cacher is the code snippet organizer for pro developers

// binary search template

// 1. search for first position using while loop
// avoid using stack in case of overflow. stack is not big.
// Timing complexity O(nlogn)

// keypoints:
// 1. start + 1 < end  (loop ends when start and end are one step away from each other)
// rate case: if you use start < end (start==1,end==2), and if you don't use mid+1 or mid-1 when updating start/end.
// There will be a infinity loop.
// 2. start + (end - start) / 2 (because start + end may overflow)
// 3. A[mid] ==, <, >  
// 4. A[start] A[end] ? target
class Solution {
  public int binarySearch(int[] A, int target) {
      if (A == null || A.length == 0) { // array could be empty and null
        return -1;
      }
      
      int start = 0;
      int end = A.length - 1;
      int mid;
      
      while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
          end = mid;
        } else if (A[mid] < target) {
          start = mid;
        } else if (A[mid] > target) {
          end = mid;
        }
      }
      
      if (A[start] == target) {
        return start;
      }
      if (A[end] == target) {
        return end;
      }
      
      return -1;
  }
}

// 2. serach for first position using recursion
// show people I can also use recursion
class Solution {
  public int binarySearch(int[] A, int target) {
      if (A == null || A.length == 0) {
        return -1;
      }
      
      int start = 0;
      int end = A.length - 1;
      int mid;
      
      while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (A[mid] == target) {
          end = start; // difference
        } else if (A[mid] < target) {
          start = mid;
        } else if (A[mid] > target) {
          end = mid;
        }
      }
      
      // difference
      if (A[end] == target) {
        return end;
      }
      if (A[start] == target) {
        return start;
      }
      
      return -1;
  }
}

// recursive
class Solution {
  public int binarySearch(int[] A, int target) {
      if (A == null || A.length == 0) {
        return -1;
      }
      
  }
  public int binarySearchFunc
}