CC-13 : Find peak element in array.

Description:

A peak element in an array is an element that is greater than its neighbors. If an element is at the first element, the element Given an input array find the peak element in the array.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 3, 22, 44, 67, 77, 96, 122, 144, 201, 133, 101,	Peak Element 201 found at index 8
Array: 3, 22, 44, 34, 67, 77, 96, 122,	Peak Element 122 found at index 7

Pseudocode:

findPeakElement(nums[]):

Integer array named nums is received as input parameter.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to nums.length-2, we will use this variable to check the last index of partition in which are searching for required integer.

Set integer variable len to nums.length.

Check if first element is peak element: if len=1 or if num[0] > nums[1], then first element of array is peak element so return 0 (index of peak element).

Check if last element is peak element: if num[len-1] > nums[len-2], then last element of array is peak element so return len-1 (index of peak element).

While (firstIdx <= lastIdx) do the following steps:

Set integer variable midCount to (lastIdx-firstIdx)/2.

Set integer variable midIdx to (firstIdx+midCount)to get mid index of current partition. We will use midIdx to partition the array into 2 parts.

If (nums[midIdx-1] < nums[midIdx] and nums[midIdx] > nums[midIdx+1]) Then we have found peak element so return midIdx.

Else if nums[midIdx] > nums[midIdx-1] then:

Set firstIdx=(midIdx+1) as we need to search in lower partition now.

Else:

Set lastIdx=midIdx-1, as we need to search in the lower partition now.

If Peak element is not found in code above return -1, as the required peak element does not exist within the input array.

Code:

public int findPeakElement(int[] nums){
	int firstIdx=0;
	int lastIdx=nums.length-2;
	int len=nums.length;
	if ((len==1)|| (nums[0]> nums[1])){return 0;}
	if (nums[len-1]> nums[len-2]){return len-1;}
	while (firstIdx <= lastIdx) {
		int midCount=(lastIdx-firstIdx)/2;
		int midIdx=firstIdx+midCount;
		if ((nums[midIdx-1]<nums[midIdx])&&(nums[midIdx]>nums[midIdx+1])) {
			return midIdx;
		} else { if (nums[midIdx]>nums[midIdx-1] ) {
			firstIdx=midIdx+1;
		}else {
			lastIdx=midIdx-1;
		}
		}		
	}	
	return -1;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchFindPeakElement {

public int findPeakElement(int[] nums){
	int firstIdx=0;
	int lastIdx=nums.length-2;
	int len=nums.length;
	if ((len==1)|| (nums[0]> nums[1])){return 0;}
	if (nums[len-1]> nums[len-2]){return len-1;}
	while (firstIdx <= lastIdx) {
		int midCount=(lastIdx-firstIdx)/2;
		int midIdx=firstIdx+midCount;
		if ((nums[midIdx-1]<nums[midIdx])&&(nums[midIdx]>nums[midIdx+1])) {
			return midIdx;
		} else { if (nums[midIdx]>nums[midIdx-1] ) {
			firstIdx=midIdx+1;
		}else {
			lastIdx=midIdx-1;
		}
		}		
	}	
	return -1;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchFindPeakElement search=new SearchFindPeakElement();
	int[] nums= { 3,22,44,67,77,96,122, 144, 201, 133,101};
	
	
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	retVal=search.findPeakElement(nums);
	System.out.println("\n\nPeak Element "+nums[retVal] + " found at index "+ retVal);	
	
	
	int[] nums1= {3,22,44,34,67,77,96,122};
	
	
	System.out.println("\nArray:");
	arrayIndex=0;
	for (arrayIndex=0; arrayIndex< nums1.length; arrayIndex++) {
		System.out.print(nums1[arrayIndex]+", ");		
	} 
	
	retVal=search.findPeakElement(nums1);
	System.out.println("\n\nPeak Element"+nums1[retVal] + " found at index "+ retVal);	
	
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}



}