Teaching Kids Programming: Videos on Data Structures and Algorithms
Linear Search Algorithm to Find Square Root
Taking sqrt(n) for example, the linear search (a kind of a bruteforce search in this case):
1 2 3 4 | def sqrt(n): for i in range(n): if i * i == n: return i |
def sqrt(n):
for i in range(n):
if i * i == n:
return iThe complexity is O(N) – linear time: here the computer exhausts the numbers in the range (search space) to find out if there is a number that is the answer. In the worst case, it can’t find such integer – then the computer needs to check N times. If the N is large, the computer may spend a significant amount of time in doing this.
Binary Search to Find Square Root
Binary search implementation:
1 2 3 4 5 6 7 8 9 10 | def sqrt(n): left, right = 0, n while left <= right: mid = (left + right) // 2 if mid * mid == n: return mid if mid * mid >= n: right = mid - 1 else: left = mid + 1 |
def sqrt(n):
left, right = 0, n
while left <= right:
mid = (left + right) // 2
if mid * mid == n:
return mid
if mid * mid >= n:
right = mid - 1
else:
left = mid + 1Complexity: O(logN). Every iteration, we half the search space (by moving corresponding left or right pointer) until we either find the answer or left and right pointer meet somewhere in the middle.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Check If an Array Represents a Max Heap (Danny Heap Algorithm)
Next Post: Two Pointer Sliding Window to Compute the Longest Substring with At Most Two Distinct Characters
