package com.algorithms.search.bitonic;

/**
 * Algorithms 4th exercise 1.4.20 Bitonic Array Search Implement
 * 算法第4版 习题 1.4.20 双调数组查找实现
 */
public class BitonicSearch {

    /**
     * 暴力搜索实现
     * @param data 数据集
     * @param key 查找数值
     * @return (-1:查找数值不存在于数据集;其他:数值所在数据集的下标序号)
     */
    public static int bruteForceSearch(int[] data, int key) {
        if (data == null || data.length == 0) {
            throw new IllegalArgumentException("Invalid data array.");
        }

        for (int i=0;i<data.length;i++) {
            if (data[i] == key) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分搜索实现
     * @param data 数据集
     * @param key 查找数值
     * @return (-1:查找数值不存在于数据集;其他:数值所在数据集的下标序号)
     */
    public static int binarySearch(int[] data, int key) {
        if (data == null || data.length == 0) {
            throw new IllegalArgumentException("Invalid data array.");
        }

        int maxIndex = BitonicSearch.getMaxIndex(data);
        if (maxIndex == -1) {
            throw new IllegalArgumentException("Invalid bitonic data array.");

        } else if (key > data[maxIndex]) {
            return -1;

        } else if (key == data[maxIndex]) {
            return  maxIndex;

        } else {
            int index = searchIncrementPart(data, maxIndex, key);
            if (index == -1) {
                index = searchDecrementPart(data, maxIndex, key);
            }
            return index;
        }
    }

    /**
     * 找出双调数组中的最大数值的下标序号
     * @param data 数据集
     * @return (-1:找不到最大值;其他:最大数值的下标序号)
     */
    private static int getMaxIndex(int[] data) {
        int start = 0;
        int end = data.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (data[mid] > data[mid - 1] &&
                    data[mid] > data[mid + 1]) {
                return mid;
            } else if (data[mid] < data[mid - 1]) {
                end = mid - 1;
            } else if (data[mid] < data[mid + 1]) {
                start = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 在双调数组递增部分查找
     * @param data 数据集
     * @param maxIndex 双调数组中的最大数值的下标序号
     * @param key 查找数值
     * @return (-1:查找数值不存在于数据集;其他:数值所在数据集的下标序号)
     */
    private static int searchIncrementPart(int[] data, int maxIndex, int key) {
        int start = 0;
        int end = maxIndex - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (data[mid] == key) {
                return mid;

            } else if (data[mid] > key) {
                end = mid - 1;

            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 在双调数组递减部分查找
     * @param data 数据集
     * @param maxIndex 双调数组中的最大数值的下标序号
     * @param key 查找数值
     * @return (-1:查找数值不存在于数据集;其他:数值所在数据集的下标序号)
     */
    private static int searchDecrementPart(int[] data, int maxIndex, int key) {
        int start = maxIndex + 1;
        int end = data.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (data[mid] == key) {
                return mid;

            } else if (data[mid] < key) {
                end = mid - 1;

            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}

@@ -215,35 +215,35 @@
 %E9%9B%86%0A     * @param 
-key
+num
  %E6%9F%A5%E6%89%BE%E6%95%B0%E5%80%BC%0A     * @re
@@ -335,35 +335,35 @@
 int%5B%5D data, int 
-key
+num
 ) %7B%0A        if (
@@ -545,27 +545,27 @@
 (data%5Bi%5D == 
-key
+num
 ) %7B%0A        
@@ -683,35 +683,35 @@
 %E9%9B%86%0A     * @param 
-key
+num
  %E6%9F%A5%E6%89%BE%E6%95%B0%E5%80%BC%0A     * @re
@@ -803,27 +803,27 @@
 %5D data, int 
-key
+num
 ) %7B%0A        
@@ -1129,19 +1129,19 @@
 lse if (
-key
+num
  %3E data%5B
@@ -1196,19 +1196,19 @@
 lse if (
-key
+num
  == data
@@ -1321,35 +1321,35 @@
 data, maxIndex, 
-key
+num
 );%0A            i
@@ -1426,19 +1426,19 @@
 xIndex, 
-key
+num
 );%0A     
@@ -2207,35 +2207,35 @@
 %E5%8F%B7%0A     * @param 
-key
+num
  %E6%9F%A5%E6%89%BE%E6%95%B0%E5%80%BC%0A     * @re
@@ -2345,35 +2345,35 @@
 t maxIndex, int 
-key
+num
 ) %7B%0A        int 
@@ -2508,35 +2508,35 @@
 f (data%5Bmid%5D == 
-key
+num
 ) %7B%0A            
@@ -2587,19 +2587,19 @@
 %5Bmid%5D %3E 
-key
+num
 ) %7B%0A    
@@ -2833,19 +2833,19 @@
  @param 
-key
+num
  %E6%9F%A5%E6%89%BE%E6%95%B0%E5%80%BC%0A  
@@ -2971,19 +2971,19 @@
 ex, int 
-key
+num
 ) %7B%0A    
@@ -3148,19 +3148,19 @@
 mid%5D == 
-key
+num
 ) %7B%0A    
@@ -3223,11 +3223,11 @@
 %5D %3C 
-key
+num
 ) %7B%0A

replace field name - 'key' to 'num'