A peak element in an array is one that is strictly greater than its neighboring elements. Given an integer array where no two adjacent values are equal, the task is to locate any peak element and return its index. Multiple peaks may exist, and returning any single peak is acceptable. The solution must achieve O(log n) time complexity.

Algorithm Strategy

Since adjacent elements in the array are guaranteed to be different, we can always determine which direction to search based on comparisons:

• Step 1: Check if the first (index 0) or last (index length-1) elements qualify as peaks
• Step 2: If boundary elements aren't peaks, examine the middle element
• Step 3: If the middle element isn't a peak, determine the search direction: if the right neighbor is larger, search the right half; if the left neighbor is larger, search the left half; if both neighbors are larger, choose either side since at least one peak exists in each direction

Java Implementation

public static int locatePeakElement(int[] data) {
    int size = data.length;
    
    // Single element case - the only element is automatically a peak
    if (size == 1) {
        return 0;
    }
    
    // Check if first element is a peak by comparing with its right neighbor
    if (data[0] > data[1]) {
        return 0;
    }
    
    // Check if last element is a peak by comparing with its left neighbor
    if (data[size - 1] > data[size - 2]) {
        return size - 1;
    }
    
    int left = 1, right = size - 2, mid = 0, result = -1;
    
    while (left <= right) {
        mid = left + (right - left) / 2;
        
        // If left neighbor is greater, peak must exist in left subarray
        if (data[mid - 1] > data[mid]) {
            right = mid - 1;
        } 
        // If right neighbor is greater, peak must exist in right subarray
        else if (data[mid] < data[mid + 1]) {
            left = mid + 1;
        } 
        // Found a peak at current position
        else {
            result = mid;
            break;
        }
    }
    
    return result;
}

C Implementation

The C version requires an additional parrameter for array length since array are passed by reference without inherent size information:

int locatePeakElement(int data[], int length) {
    if (length == 1) {
        return 0;
    }
    
    if (data[0] > data[1]) {
        return 0;
    }
    
    if (data[length - 1] > data[length - 2]) {
        return length - 1;
    }
    
    int left = 1, right = length - 2, mid = 0, result = -1;
    
    while (left <= right) {
        mid = left + (right - left) / 2;
        
        if (data[mid - 1] > data[mid]) {
            right = mid - 1;
        }
        else if (data[mid] < data[mid + 1]) {
            left = mid + 1;
        }
        else {
            result = mid;
            break;
        }
    }
    
    return result;
}