35. Search Insert Position

const int ZERO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    int searchInsert3(const vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1, mid = 0;

        while(left <= right)
        {
            mid = (left + right) / 2;

            if(target > nums[mid])
            {
                left = mid + 1;
            }
            else if(target < nums[mid])
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }   

        return mid + (target > nums[mid]);
    }

    int searchInsert2(const vector<int>& nums, int target) 
    {
        int from = 0, size = int(nums.size());

        for(int j = size >> 1; j >= 1; j = j >> 1)
        {
            while(from + j < size && target >= nums[from + j])
            {
                from += j;
            }
        } 

        return from + (target > nums[from]);
    }

    int searchInsert1(const vector<int>& nums, int target) 
    {
        int index = 0, first = 0, step = 0, count = nums.size();

        while(count) 
        {
            index = first;
            
            step = count >> 1;
            
            index += step;
            
            if(nums[index] < target) 
            {
                first = ++index;

                count -= step + 1;
            } 
            else 
            {
                count = step;
            }
        }
        
        return first;    
    } 

    // left - позиция элемента < target
    // right - позиция элемента >= target
    
    int searchInsert(const vector<int>& nums, int target) 
    {
        int left = -1, right = nums.size(), mid = 0;

        while(right - left > 1)
        {
            mid = left + ((right - left) >> 1);

            if(nums[mid] < target)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }

        return right;
    }     
};