0
$\begingroup$

this is a popular searching problem and the question is :

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers = [2,7,11,15], target = 9 Output: [1,2]

Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Now i know that it can be solved using 2-pointer method,hashing and binary search.

If i use binary search,it goes like fix the first element A[0] and do binary search on the remaining n-1 elements. If cannot find any element which equals target-A[0], Try A[1]. That is, fix A[1] and do binary search on A[2]~A[n-1]. Continue this process until we have the last two elements A[n-2] and A[n-1].

what will be the time complexity if i use binary search ? is not it O(nlgn)?as in the worst case, we have to go extreme right. Somewhere it is mentioned that the worst case is still o(n) while average case is O(lgn).

Let me know if O(nlgn) is wrong and the reason.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.