SDE - 2

The Simple Approach is to find the floor of the square root, try with all-natural numbers starting from 1. Continue incrementing the number until the square of that number is greater than the given number.

Algorithm : 
1. Create a variable (counter) i and take care of some base cases, i.e when the given number is 0 or 1.
2. Run a loop until i*i <= n , where n is the given number. Increment i by 1.
3. The floor of the square root of the number is i – 1
 

Time Complexity: O(√ n). 
 

The Better Approach would be to use Binary Search. The idea is to find the largest integer i whose square is less than or equal to the given number. The values of i * i is monotonically increasing, so the problem can be solved using binary search. 
 

Algorithm : 
1. Take care of some base cases, i.e when the given number is 0 or 1.
2. Create some variables, lowerbound l = 0, upperbound r = n, where n is the given number, mid and ans to store the answer.
3. Run a loop until l <= r , the search space vanishes
4. Check if the square of mid (mid = (l + r)/2 ) is less than or equal to n, If yes then search for a larger value in second half of search space, i.e l = mid + 1, update ans = mid
5. Else if the square of mid is more than n then search for a smaller value in first half of search space, i.e r = mid – 1
6. Print the value of answer.
 

Time Complexity : O(log(n))

The brute force solution is to traverse the entire array and find the minimum. Time Complexity : O(N)

The efficient approach is to use Binary Search. The following pattern can be observed : 
 

• The minimum element is the only element whose previous is greater than it. If there is no previous element, then there is no rotation (the first element is minimum). We check this condition for the middle element by comparing it with (mid-1)’th and (mid+1)’th elements.
 

• If the minimum element is not at the middle (neither mid nor mid + 1), then the minimum element lies in either the left half or right half. 
1. If the middle element is smaller than the last element, then the minimum element lies in the left half
2. Else minimum element lies in the right half.
 

Pseudocode:

Low = 0
High = n-1
findMin(arr,low, high)
{
	while(low < high)
	{
		mid = low + (high - low)/2
		if (arr[mid] == arr[high])
			high--
		else if(arr[mid] > arr[high])
			low = mid + 1
		else
			high = mid
	}
	return arr[high]
}