# 双调数组( bitonic array )的高效( ~2lgN )搜索

### 原题

Search in a bitonic array. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of n distinct integer values, determines whether a given integer is in the array.

Standard version: Use ∼3lgn compares in the worst case.

Signing bonus: Use ∼2lgn compares in the worst case (and prove that no algorithm can guarantee to perform fewer than ∼2lgn compares in the worst case).

### 解题

#### 基础版：在最坏的情况下时间复杂度~3lgN实现。

 `````` 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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 `````` `````` import edu.princeton.cs.algs4.StdOut; /** * @author elong * @version V1.0 * @date 04/12/2017 */ public class BitonicArray { public static void main(String[] args) { int[] a = {1, 2, 3, 4, 5, 6, 7, 10, 29, 28, 27, 23, 22, 19, 17}; int result = find(a, 6); StdOut.println(result); } public static int find(int[] a, int key) { int maxIdx = findTheMaxIdx(a); if (key == a[maxIdx]) { return maxIdx; } int first = findFirst(a, maxIdx, key); if (first != -1) { return first; } return findLast(a, maxIdx, key); } /** * Use the binary search find max value * ~lgN */ public static int findTheMaxIdx(int[] a) { int lo = 0; int hi = a.length - 1; while (lo < hi) { int mid = (lo + hi) / 2; if (a[mid] > a[mid + 1]) { hi = mid; } else { lo = mid + 1; } } return hi; } /** * Use the binary search find the increasing sequence * ~lgN */ private static int findFirst(int[] a, int maxIdx, int key) { int loIdx = 0; int hiIdx = maxIdx; while (loIdx <= hiIdx) { int mid = (loIdx + hiIdx) / 2; if (a[mid] > key) { hiIdx = mid - 1; } else if (a[mid] < key) { loIdx = mid + 1; } else { return mid; } } return -1; } /** * Use the binary search find the decreasing sequence * ~lgN */ private static int findLast(int[] a, int maxIdx, int key) { int loIdx = maxIdx; int hiIdx = a.length - 1; while (loIdx <= hiIdx) { int mid = (loIdx + hiIdx) / 2; if (a[mid] < key) { hiIdx = mid - 1; } else if (a[mid] > key) { loIdx = mid + 1; } else { return mid; } } return -1; } } ``````

#### 进阶版：在最坏的情况下时间复杂度~2lgN 实现。

##### 1) 对原文概述分析

The key insight is that if you know a[lo] <= key < a[hi] (The open inequality for a[hi] is important!), then you can use a binary search on the semi-open range [lo,hi), even if a is bitonic.

##### 2) 对原文论证分析

Proof: If a is bitonic in the range [lo,hi), then we can divide up the range into [lo, k), [k, peak), [peak, hi) where k is the first index with a[k] > a[hi].  We know the answer can only fall into the first region, [lo,k), since key < a[hi] < a[k], so everything in the second two regions are necessarily > key.

##### 3) 本题的解题思路

 `````` 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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 `````` `````` public class FastBitonicArraySearch { private static boolean leftSearch(int[] a, int key, int lo, int hi) { while (lo < hi - 1) { int mid = (lo + hi) / 2; if (key < a[mid]) { hi = mid; } else { lo = mid; } } return key == a[lo]; } private static boolean rightSearch(int[] a, int key, int lo, int hi) { while (lo < hi - 1) { int mid = (lo + hi) / 2; if (key < a[mid]) { lo = mid; } else { hi = mid; } } return key == a[hi]; } public static boolean bitonicSearch(int[] a, int key) { int lo = 0, hi = a.length - 1; while (lo < hi - 1) { int mid = (lo + hi) / 2; if (key < a[mid]) { return leftSearch(a, key, lo, mid) || rightSearch(a, key, mid, hi); } else { if (a[mid] < a[mid + 1]) { lo = mid; } else { hi = mid; } } } return key == a[lo] || key == a[hi]; } /** * Test OutPut: * 1 is in array? true * 2 is in array? true * 3 is in array? true * 4 is in array? true * 5 is in array? true * 6 is in array? true * 29 is in array? true * 28 is in array? true * 27 is in array? true * 23 is in array? true * 22 is in array? true * 19 is in array? true * 17 is in array? true * 16 is in array? true * 15 is in array? true * 14 is in array? true * 13 is in array? true * 12 is in array? true * 11 is in array? true * 10 is in array? true * 9 is in array? true * 8 is in array? true * 7 is in array? true * 1000 is in array? false * 0 is in array? false */ public static void main(String[] args) { int[] a = {1, 2, 3, 4, 5, 6, 29, 28, 27, 23, 22, 19, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7}; for (int i : a) { boolean b = bitonicSearch(a, i); System.out.println(i + " is in array? " + b); } System.out.println("1000 is in array? " + bitonicSearch(a, 1000)); System.out.println("0 is in array? " + bitonicSearch(a, 0)); } } ``````