MountainBinarySearch

import java.util.Comparator;

public class IncreasingDecreasingBinarySearch {
	public static void main(String []argv) {
		IncreasingDecreasingBinarySearch idbs = new IncreasingDecreasingBinarySearch();

		int []num = new int[]{1, 3, 4, 5, 7, 8, 2, 0};

		System.out.println(num[idbs.search(num, 1)]);
		System.out.println(num[idbs.search(num, 2)]);
		System.out.println(num[idbs.search(num, 3)]);
		System.out.println(num[idbs.search(num, 4)]);
		System.out.println(num[idbs.search(num, 5)]);
		System.out.println(num[idbs.search(num, 7)]);
		System.out.println(num[idbs.search(num, 8)]);
		System.out.println(num[idbs.search(num, 0)]);
	}

	public int findPeak(int []num) {
		if (num.length == 1) {
			return 0;
		}

		int min = 0;
		int max = num.length - 1;
		int mid = min + (max - min) / 2;

		while (min <= max) {
			mid = min + (max - min) / 2;
			if ((mid == 0 && num[mid] > num[mid + 1]) ||
				(mid == num.length - 1 && num[mid] > num[mid - 1]) ||
				(num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) ) {
				return mid;
			} else if (num[mid + 1] > num[mid]) {
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
		return -1; // should not happen
	}

	public int search(int []num, int target) {
		int peakIndex = findPeak(num);
		if (num[peakIndex] == target) {
			return peakIndex;
		}

		int increasingIndex = binarySearch(num, 0, peakIndex - 1, target, new Comparator<Integer>() {
			@Override
			public int compare(Integer a, Integer b) {
				return a - b;
			}
		});

		int decreasingIndex = binarySearch(num, peakIndex + 1, num.length - 1, target, new Comparator<Integer>() {
			@Override
			public int compare(Integer a, Integer b) {
				return b - a;
			}
		});

		return (increasingIndex == -1) ? decreasingIndex : increasingIndex;
	}

	private int binarySearch(int []num, int min, int max, int target, Comparator<Integer> comp) {
		while (min <= max) {
			int mid = min + (max - min) / 2;
			if (num[mid] == target) {
				return mid;
			} else if (comp.compare(target, num[mid]) > 0) {
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
		return -1;
	}
/*
	private int findDecreasing(int []num, int min, int max, int target) {
		while (min <= max) {
			int mid = min + (max - min) / 2;
			if (num[mid] == target) {
				return mid;
			} else if (target < num[mid]) {
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
		return -1;
	}

	private int findIncreasing(int []num, int min, int max, int target) {
		while (min <= max) {
			int mid = min + (max - min) / 2;
			if (num[mid] == target) {
				return mid;
			} else if (target > num[mid]) {
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
		return -1;
	}
	*/
}