题解 | #二分查找-I#

递归本身自带循环，只需要条件判断

class Solution {
public:
    void half_search(int low, int high, std::vector<int> &nums, int target, int &index) {
      if (low <= high) {   // 继续递归的条件
        int mid = (low+high) / 2;
        if (nums[mid] == target) {  // 找到，终止递归
          index = mid;
          return ;
        }
        if (nums[mid] < target) {
          half_search(mid+1, high, nums, target, index);
        } else {
          half_search(low, mid-1, nums, target, index);
        }
      }
      // 没找到一直回退到顶层
    }
  
    int search(vector<int>& nums, int target) {
      if (nums.empty()) {  // 边界
        return -1;
      }
      
      int index = -1;
      
      half_search(0, nums.size()-1, nums, target, index);
      
      return index;
    }
};

迭代，每次手动更改上下边界

class Solution {
public:
    int search(vector<int>& nums, int target) {
      if (nums.empty()) {
        return -1;
      }
      int low = 0, high = nums.size()-1;
      
      while (low <= high) {
        int mid = (low+high) / 2;
        if (nums[mid] == target) {
          return mid;
        } else if (nums[mid] > target) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      return -1;
    }
};