/*
 * BF:  O(N)
 */
class Solution {
public:
  bool search(vector& nums, int target) {
    for(auto itr = nums.begin(); itr != nums.end(); itr++) {
      if (*itr == target) return true;
    }
    return false;
  }
};

/*
 * 
 */
class Solution {
public:
  bool search(vector& nums, int target) {
    if (nums.size() < 1) return false;
    if (nums.size() == 1) return nums[0] == target;
    //  target
    //  target 
    int begin = 0;
    while (begin + 1 < nums.size()) {
      if (nums[begin] == target || nums[begin + 1] == target) return true;
      if (nums[begin] > nums[begin + 1]) break;
      begin++;
    }

    // 
    int end = nums.size();
    while (begin + 1 < end && end