二分法题目

• Search in Rotated sorted array (leetcode 33)

  class Solution {
  public:
      int search(vector<int>& nums, int target) {
          // find pivot
          int l=0, r=nums.size()-1;
          while(l<r){
              int m = l + (r - l) / 2;
              if(nums[m] > nums[r]) l = m + 1;
              else r = m;
          }
          // normal binary search
          int idx;
          idx = lower_bound(nums.begin(), nums.begin()+l, target) - nums.begin();
          if(idx < l && nums[idx] == target) return idx;
          idx = lower_bound(nums.begin()+l, nums.end(), target) - (nums.begin()+l);
          if(l+idx < nums.size() && nums[l+idx] == target) return idx+l;
          return -1;
      }
  };
  

• Search in Duplicated & Rotated sorted array (leetcode 154)

  class Solution {
  public:
      int findMin(vector<int>& nums) {
          int N = nums.size();
          if(!N) return false;
  
          // find pivot
          int l=0, r=N-1;
          while(l<r){
              int m = l+(r-l)/2;
              if(nums[l] == nums[r]) l++; // remove duplication
              else if(nums[m] > nums[r]) l = m+1;
              else r = m;
          }
  
          return min(nums[0], nums[l]);
      }
  };
  

• Use std correctly, especially when not found.

  leetcode 34.

  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          if(nums.empty()) return vector<int>(2, -1);
          vector<int> ans;
          int a = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
          int b = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
          cout<<a<<" "<<b<<endl;
          // not found exception
          if(a>=nums.size() || nums[a] != target) ans.push_back(-1);
          else ans.push_back(a);
          if(b-1>=nums.size() || nums[b-1] != target) ans.push_back(-1);
          else ans.push_back(b-1);
          return ans;
      }
  };
  

• Split Array Largest Sum leetcode 410

  ```c++ class Solution { public: #define ll long long bool check(vector& nums, ll mid, int m){ int cnt = 0; ll sum = 0; for(int i=0; i mid){ sum = nums[i]; cnt++; if(cnt >= m) return true; } } return false; }

  int splitArray(vector<int>& nums, int m) {
      ll sum=0;
      int mx = 0;
      for(int i=0; i<nums.size(); i++){
          sum += nums[i];
          mx = max(mx, nums[i]);
      }
      ll left = mx, right = sum;
      while(left<right){
          ll mid = (left + right) / 2;
          if(check(nums, mid, m)) left = mid + 1;
          else right = mid;
      }
      return int(left);
  
  }
  

  }; ```

• 寻找最近数

  ```python T = int(input())

  data = input() S = [int(ele) for ele in data.split()]

  def solve(S, T): S.sort() i = 0 j = len(S) - 1 res = S[i] + S[j] while i < j: cur_val = S[i] + S[j] if abs(cur_val - T) < abs(res - T) or abs(cur_val - T) == abs(res - T) and cur_val < res: res = cur_val if cur_val == T: break elif cur_val < T: i = i + 1 else: j = j - 1 return res print(solve(S, T)) ```