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

    }
};