Search is always an interesting question to solve depending upon the constraints of the problem.
Let's take up the following problem for discussion: You need to find within a given number of integers whether the sum of 2 integers is equal to a given sum.
for (int i= 0; i less than n; i++ )
for (int j=0; j less than n; j++)
if(arr[i]]+arr[j] == sum)
return true;
}
}
The above solution would be of complexity O(n^2). Suppose if you have a large set of numbers the overhead would be huge;
The second alternative could be to sort the numbers and then have 2 pointers one moving from '0' other from 'n-1' both approaching each other with a logic that n-1 would move till the rightmost number is less than the sum while the leftmost would move from 0 towards the right so that
a[leftmost]+a[rightmost] == sum;
This strategy would have issues where you need to sort the numbers first which has its own complexity and the total complexity would be
sortComplexity + n log(n) .. where the binary search would cut the number by half each time which is logarithmic in nature.
If we were looking for a linear solution, we can have another alternative like,
This strategy would have a linear complexity since the search is linear and the lookup in a set as well is constant.
The implementation for this idea in python is below.
def search(givenList, s):
complements = set()
for i in range(len(givenList)):
if givenList[i] in complements:
return True
complements.add(s - givenList[i])
return False
if __name__ == '__main__':
given = [10, 7, 8, 24, 46, 3 , 86, 35]
result = search(given,93)
print(result)
pass
Let's take up the following problem for discussion: You need to find within a given number of integers whether the sum of 2 integers is equal to a given sum.
A naive solution to this problem would be
for (int i= 0; i
return true;
}
}
The above solution would be of complexity O(n^2). Suppose if you have a large set of numbers the overhead would be huge;
The second alternative could be to sort the numbers and then have 2 pointers one moving from '0' other from 'n-1' both approaching each other with a logic that n-1 would move till the rightmost number is less than the sum while the leftmost would move from 0 towards the right so that
a[leftmost]+a[rightmost] == sum;
This strategy would have issues where you need to sort the numbers first which has its own complexity and the total complexity would be
sortComplexity + n log(n) .. where the binary search would cut the number by half each time which is logarithmic in nature.
If we were looking for a linear solution, we can have another alternative like,
- Take converse of each number (sum - current)
- Store in a set (Hash Set in some cases) // which holds unique values
- Check if the coming numbers exist in the set already.
- if the number exists return true else false.
This strategy would have a linear complexity since the search is linear and the lookup in a set as well is constant.
The implementation for this idea in python is below.
def search(givenList, s):
complements = set()
for i in range(len(givenList)):
if givenList[i] in complements:
return True
complements.add(s - givenList[i])
return False
if __name__ == '__main__':
given = [10, 7, 8, 24, 46, 3 , 86, 35]
result = search(given,93)
print(result)
pass
