# 75.Find Peak Element

## 1.Description(Medium)

There is an integer array which has the following features:

* The numbers in adjacent positions are different.
* A\[0] < A\[1]  && A\[A.length - 2] > A\[A.length - 1].

We define a position P is a peek if:

```
A[P] > A[P-1] & A[P] > A[P+1]
```

Find a peak element in this array. Return the index of the peak.

### Notice

The array may contains multiple peeks, find any of them.

**Example**

Given`[1, 2, 1, 3, 4, 5, 7, 6]`

Return index`1`(which is number 2) or`6`(which is number 7)

[**Challenge**](https://www.lintcode.com/en/problem/find-peak-element/#challenge)

Time complexity O(logN)

## 2.Code

以下只适用于lintcode,因为Lintcode的题目限制了A\[0] < A\[1] && A\[A.length - 2] > A\[A.length - 1].，所以可以start=1;end=length-2;

但是leetcode没有限制，所以词方法不行。

```
public int findPeak(int[] A){
        if(A==null || A.length==0){
            return -1;
        }
        //caution: start and end;
        int start=1;
        int end=A.length-2;
        while(start+1<end){
            int mid=start+(end-start)/2;
            //top directly return 
            if(position(A,mid)==2){
                return mid;
            }
            //increase 
            else if(position(A,mid)==1){
                start=mid;
            }
            //decrease
            else if(position(A,mid)==-1){
                end=mid;
            }
            //bottom
            else if(position(A,mid)==-2){
                start=mid;  //or end =mid;
            }
        }
        if(position(A,start)==2){
            return start;
        }
        if(position(A,end)==2){
            return end;
        }
        return -1;
    }


    public int position(int[] A,int mid){
        int middle=A[mid];
        int pre=A[mid-1];
        int post=A[mid+1];
        //bottom
        if(middle<pre && middle<post){
            return -2;
        }  
        //decrease
        else if(middle<pre && middle>post){
            return -1;
        }
        //top
        else if(middle>pre && middle>post){
            return 2;
        }
        //increase
        else if(middle>pre && middle<post){
            return 1;
        }
        return 0;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/1.binary-search/75find-peak-element.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.