c++ implementation with binary search


  • 0
    A

    I advise to always divide your code to block and give reasonable names to methods. 1) It will be more readable. 2) We can test methods separately.

    class Solution {
    public:
        // the method get vector by reference, so it prevent to copy whole vector
        int binSearch(vector<int>& nums, int target) {
            // we have nums.size() indexes, but num.size() + 1 possible output
    
            // so first of all we check first special case
            if (target < nums[0]) return 0;
            // we looking for index in range [left, right)
            // in binSearch target always greater than nums[left]
            int left = 0, right = nums.size();
            while (left < right) {
                int middle = (left + right) / 2;
                // if we found target value we return index
                if (nums[middle] == target) return middle;
                if (nums[middle] > target) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            // finally we return left index, cos nums[left] > left
            return left;
        }
        int searchInsert(vector<int>& nums, int target) {
            // special case
            if (nums.size() < 1) return 0;
            // binSearch method
            int index = binSearch(nums, target);
            return index;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.