35. 搜索插入位置

//方法1(二分)
int search(vector<int> arr, int num) {
    int l = 0, r = arr.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == num)
            return mid;
        else if (arr[mid] < num)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int searchInsert(vector<int> &nums, int target) {
    int arr[nums.size()], index = 0;
    copy(nums.begin(), nums.end(), arr);
    if (search(nums, target) != -1)
        return search(nums, target);
    else if (target >= nums[0] || target <= nums[nums.size() - 1])
        index = lower_bound(arr, arr + nums.size(), target) - arr;
    else if (target > nums[nums.size() - 1])
        index = nums.size();
    return index;
}

//方法2(二分位运算)
int searchInsert(vector<int> &nums, int target) {
    int l = 0, r = nums.size(), mid = l + ((r - l) >> 1);
    while (l < r) {
        if (nums[mid] < target)
            l = mid + 1;
        else if (nums[mid] > target)
            r = mid;
        else
            return mid;
        mid = l + ((r - l) >> 1);
    }
    return mid;
}