Applications of algorithms.

[badallogical]

Like how binary search are used in rotated array , peak finding , square root etc. and similarly other algorithms application.

[sumitgsh]

Okay can you assign me the above one

[panchiwalashivani]

Peak finding

The idea is based on the technique of Binary Search to check if the middle element is the peak element or not. If the middle element is not the peak element, then check if the element on the right side is greater than the middle element then there is always a peak element on the right side. If the element on the left side is greater than the middle element then there is always a peak element on the left side. Form a recursion and the peak element can be found in log n time.

Algorithm:

Create two variables, l and r, initilize l = 0 and r = n-1
Iterate the steps below till l <= r, lowerbound is less than the upperbound
Check if the mid value or index mid = (l+r)/2, is the peak element or not, if yes then print the element and terminate.
Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update r = mid – 1
Else if the element on the right side of the middle element is greater then check for peak element on the right side, i.e. update l = mid + 1

// A Java program to find a peak
// element using divide and conquer
import java.util.;
import java.lang.;
import java.io.*;

class PeakElement {
// A binary search based function
// that returns index of a peak element
static int findPeakUtil(
int arr[], int low, int high, int n)
{
// Find index of middle element
// (low + high)/2
int mid = low + (high - low) / 2;

	// Compare middle element with its 
	// neighbours (if neighbours exist) 
	if ((mid == 0 || arr[mid - 1] <= arr[mid]) 
		&& (mid == n - 1 || arr[mid + 1] <= arr[mid])) 
		return mid; 

	// If middle element is not peak 
	// and its left neighbor is 
	// greater than it, then left half 
	// must have a peak element 
	else if (mid > 0 && arr[mid - 1] > arr[mid]) 
		return findPeakUtil(arr, low, (mid - 1), n); 

	// If middle element is not peak 
	// and its right neighbor 
	// is greater than it, then right 
	// half must have a peak 
	// element 
	else
		return findPeakUtil( 
			arr, (mid + 1), high, n); 
} 

// A wrapper over recursive function 
// findPeakUtil() 
static int findPeak(int arr[], int n) 
{ 
	return findPeakUtil(arr, 0, n - 1, n); 
} 

// Driver method 
public static void main(String[] args) 
{ 
	int arr[] = { 1, 3, 20, 4, 1, 0 }; 
	int n = arr.length; 
	System.out.println( 
		"Index of a peak point is " + findPeak(arr, n)); 
} 

}

[panchiwalashivani]

Square root

Approach :

1. As the square root of number lies in range 0 <= squareRoot <= number, therefore, initialize start and end as : start = 0, end = number.
2. Compare the square of mid integer with the given number. If it is equal to the number, then we found our integral part, else look for the same in left or right side depending upon the scenario.
3. Once we are done with finding the integral part, start computing the fractional part.
4. Initialize the increment variable by 0.1 and iteratively compute the fractional part upto p places. For each iteration, increment changes to 1/10th of it’s previous value.
5. Finally return the answer computed

// Java implementation to find
// square root of given number
// upto given precision using
// binary search.
import java.io.*;

class GFG {

// Function to find square root 
// of given number upto given 
// precision 
static float squareRoot(int number, int precision) 
{ 
	int start = 0, end = number; 
	int mid; 

	// variable to store the answer 
	double ans = 0.0; 

	// for computing integral part 
	// of square root of number 
	while (start <= end) 
	{ 
		mid = (start + end) / 2; 
		
		if (mid * mid == number) 
		{ 
			ans = mid; 
			break; 
		} 

		// incrementing start if integral 
		// part lies on right side of the mid 
		if (mid * mid < number) { 
			start = mid + 1; 
			ans = mid; 
		} 

		// decrementing end if integral part 
		// lies on the left side of the mid 
		else { 
			end = mid - 1; 
		} 
	} 

	// For computing the fractional part 
	// of square root upto given precision 
	double increment = 0.1; 
	for (int i = 0; i < precision; i++) { 
		while (ans * ans <= number) { 
			ans += increment; 
		} 

		// loop terminates when ans * ans > number 
		ans = ans - increment; 
		increment = increment / 10; 
	} 
	return (float)ans; 
} 

// Driver code 
public static void main(String[] args) 
{ 
	// Function calling 
	System.out.println(squareRoot(50, 3)); 

	// Function calling 
	System.out.println(squareRoot(10, 4)); 
} 

}

[panchiwalashivani]

Rotated Array

Approach:

The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
Using the above statement and binary search pivot can be found.
After the pivot is found out divide the array in two sub-arrays.
Now the individual sub – arrays are sorted so the element can be searched using Binary Search.

/* Java program to search an element
in a sorted and pivoted array*/

class Main {

/* Searches an element key in a 
pivoted sorted array arrp[] 
of size n */
static int pivotedBinarySearch(int arr[], int n, int key) 
{ 
	int pivot = findPivot(arr, 0, n - 1); 

	// If we didn't find a pivot, then 
	// array is not rotated at all 
	if (pivot == -1) 
		return binarySearch(arr, 0, n - 1, key); 

	// If we found a pivot, then first 
	// compare with pivot and then 
	// search in two subarrays around pivot 
	if (arr[pivot] == key) 
		return pivot; 
	if (arr[0] <= key) 
		return binarySearch(arr, 0, pivot - 1, key); 
	return binarySearch(arr, pivot + 1, n - 1, key); 
} 

/* Function to get pivot. For array 
3, 4, 5, 6, 1, 2 it returns 
3 (index of 6) */
static int findPivot(int arr[], int low, int high) 
{ 
	// base cases 
	if (high < low) 
		return -1; 
	if (high == low) 
		return low; 

	/* low + (high - low)/2; */
	int mid = (low + high) / 2; 
	if (mid < high && arr[mid] > arr[mid + 1]) 
		return mid; 
	if (mid > low && arr[mid] < arr[mid - 1]) 
		return (mid - 1); 
	if (arr[low] >= arr[mid]) 
		return findPivot(arr, low, mid - 1); 
	return findPivot(arr, mid + 1, high); 
} 

/* Standard Binary Search function */
static int binarySearch(int arr[], int low, int high, int key) 
{ 
	if (high < low) 
		return -1; 

	/* low + (high - low)/2; */
	int mid = (low + high) / 2; 
	if (key == arr[mid]) 
		return mid; 
	if (key > arr[mid]) 
		return binarySearch(arr, (mid + 1), high, key); 
	return binarySearch(arr, low, (mid - 1), key); 
} 

// main function 
public static void main(String args[]) 
{ 
	// Let us search 3 in below array 
	int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 }; 
	int n = arr1.length; 
	int key = 3; 
	System.out.println("Index of the element is : "
					+ pivotedBinarySearch(arr1, n, key)); 
} 

}

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale]

Please reopen this issue once you add more information and updates here. If this is not the case and you need some help, feel free to seek help from our Gitter or ping one of the reviewers. Thank you for your contributions!