LEETCODE/findInMountainArray.java at master · Salah856/LEETCODE · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
	public int findInMountainArray(int target, MountainArray mArr) {
		int s=0;
		int e=mArr.length()-1;
		int p=pivot(mArr,target,s,e);

		if(mArr.get(p)<target){
			return -1;
		}
		if(mArr.get(p)==target){
			return p;
		}

		int ans=search(mArr,target,0,p-1,true);
		if(ans==-1)
		ans=search(mArr,target,p+1,mArr.length()-1,false);

		return ans;
	}

	int pivot(MountainArray mArr,int target,int s, int e){
		while(s<=e){
			int m=(s+e)/2;
			if(m>0 && mArr.get(m-1)<mArr.get(m) && mArr.get(m+1)<mArr.get(m)){
				return m;
			}else if(mArr.get(m+1)>mArr.get(m)){
				s=m+1;
			}else if(mArr.get(m+1)<mArr.get(m)){
				e=m-1;
			}
		}
		return -1;
	}

	int search(MountainArray mArr,int target,int s, int e,boolean asc){
		while(s<=e){
			int m=(s+e)/2;

			if(mArr.get(m)==target){
				return m;
			}
			if(mArr.get(m)<target){
				if(asc){
					s=m+1;
				} else {
					e=m-1;
				}
			}else {
				if(asc){
					e=m-1;
				} else {
					s=m+1;
				}
			}
		}
		return -1;
	}

}