题解 | #二分查找-I#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param target int整型
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        if (nums.size() == 0)return -1;
        if (nums.size() == 1) {
            if (nums[0] == target)return 0;
            else return -1;
        }
        int length = nums.size();
        int res = 0;
        while (length) {
            if (nums[length / 2] > target) {
                vector<int>::const_iterator be = nums.begin();
                vector<int>::const_iterator en = nums.begin() + (length / 2);
                if (length != 1)nums.assign(be, en);
                else return -1;
            } else if (nums[length / 2] < target) {
                vector<int>::const_iterator be = nums.begin() + (length / 2) + 1;
                vector<int>::const_iterator en = nums.end();
                if (length != 1)nums.assign(be, en);
                else return -1;
                res += length / 2 + 1;
            } else {
                res += length / 2;
                return res;
            }
            length = nums.size();
        }

        return -1;
    }
};

比较简单，要注意的一个细节就是vector容器的assign方法中第二个参数（即结束迭代器）指示的是截取到这个迭代器前一个位置。

时间复杂度Ologn，空间复杂度为常数。