Binary Search

[xiedaxia1hao]

Order-agnostic Binary Search Leetcode 374. Guess Number Higher or Lower Leetcode 367. Valid Perfect Square 33. Search in Rotated Sorted Array 35. Search Insert Position 458. Last Position of Target (Lintcode) 34. Search for a Range 162. Find Peak Element 153. Find Minimum in Rotated Sorted Array (怎么求旋转数组里的最大值也要会） 154. Find Minimum in Rotated Sorted Array II (怎么求旋转数组里的最大值也要会） Grokking. Search in a Sorted Infinite Array Grokking. Bitonic Array Maximum: 从双调数组中找到最大的数字 Grokking. Search Bitonic Array: 从双调数组中找到target数字 Grokking. Rotation Count

总结下来大概会有这一些题：

• 基本的二分法查sorted array的target
• 求旋转数组的最大最小值
• 双调数组中找peak

Binary Search

用途：针对Sorted数组查找的算法 时间复杂度: O(log(n))

二分查找法的前置条件要拥有一个已经Sorted好的序列，这样在查找所要查找的元素时, 首先与序列中间的元素进行比较, 如果大于这个元素, 就在当前序列的后半部分继续查找, 如果小于这个元素, 就在当前序列的前半部分继续查找, 直到找到相同的元素, 或者所查找的序列范围为空为止.

伪代码:

left = 0, right = n -1
while (left <= right)
    mid = (left + right) / 2
    case
        x[mid] < t:    left = mid + 1;
        x[mid] = t:    p = mid; break;
        x[mid] > t:    right = mid -1;
return -1;

参考资料： Binary Search 总结帖 (更新完) Binary Search的总结帖 Grokking. Modified Binary Search

[xiedaxia1hao]

模版

策略是95%的情况下都用以下模板：

def binarySearch(arr, target):
    l , r = 0, len(arr) - 1  
    while l <= r:            
        mid = (l+r)//2
        if arr[mid] == target:
            return mid
        if target > arr[mid]:
            l = mid + 1
        else:
            r = mid - 1 
    return -1

极个别情况会采用以下的模板：

def binary_search(array, target):
    start, end = 0, len(array) - 1
    while start + 1 < end:
        mid = (start + end) / 2
        if array[mid] == target:
            start = mid
        elif array[mid] < target:
            start = mid
        else:
            end = mid

    if array[start] == target:
        return start
    if array[end] == target:
        return end
    return -1

至于为什么不采用一个模板，是因为在大部分题的时候，运用第一种模板能够有更好的可读性

而第二个模板专门针对的是第一个模板的短板：当要access数组边界的数，如果边界的数在运行中出现更改，可能越界。虽然这种情况也可以用Edge Case来写，但太过麻烦。这点我们后面具体说来。

这里插一句话：用的惯的模板才是最适合你的，切记

Order-Agnostic Binary Search模版

有些时候，虽然我们知道array是sorted的，但是我们不知道是升序的还是降序的。

通常情况下，我们说的sorted都是升序的，但是做题的时候，我们也有可能碰见降序的数组，甚至可能会碰见既有升序的，也有降序的Bitonic Array。

所以这里介绍一下Order-Agnostic Binary Search的模版。

public static int binarySearch(int[] arr, int left, int right, int key) {
  boolean isAscending = arr[left] < arr[right];

  while(left <= right) {
    int mid = left + (right-left)/2;
    if(arr[mid] == key) return mid;

    if(isAscending) {
      if(arr[mid] < key) left = mid+1;
      else right = mid-1;
    } else {
      if(arr[mid] < key) right = mid-1;
      else left = mid+1;
    }
  }

  return -1;
}

[xiedaxia1hao]

题型

题目类型分为三类:

1. 有明确Target
2. 没有明确Target
3. 没有明确Target (可越界类型）

[xiedaxia1hao]

第一类题：有明确Target的题型

这一类题，会要求你找一个Target值，一般找到就返回Target值的下标或者Boolean函数。基础题目举两个例子：

Leetcode 374. Guess Number Higher or Lower

猜数字游戏的规则如下： 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）： -1：我选出的数字比你猜的数字小 pick < num 1：我选出的数字比你猜的数字大 pick > num 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num 返回我选出的数字。

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while(left <= right) {
            int mid = left + (right - left)/2;
            int guess = guess(mid);

            if(guess == 0) {
                return mid;
            } else if(guess == -1) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }

        return -1;
    }
}

Leetcode 367. Valid Perfect Square

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。 进阶：不要 使用任何内置的库函数，如  sqrt 。

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1, right = num;

        while(left <= right) {
            long mid = left + (right-left)/2;

            if(mid * mid == num) {
                return true;
            } else if(mid * mid < num) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return false;
    }
}

由于这一类题基本上就是套公式，直接考公式的几率很小。所以Medium以上的题目会对边界的选定模糊化，我们要做的是明确边界，然后再套公式。下面举例二分经典题：

33. Search in Rotated Sorted Array

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

取中间值以后会发现，左边或者右边，至少有一边是sorted的，根据这个特性，就能理解下一段的代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;

        while(left <= right) {
            int mid = left + (right-left)/2;

            if(nums[mid] == target) {
                return mid;
            }

            // the left part is sorted, 一定要注意这里的等号一定要取
            // If nums[left] <= nums[mid], the numbers from start to middle are sorted in ascending order.

            if(nums[left] <= nums[mid]) {
                if(nums[left] <= target && target <= nums[mid]) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            } else {
                if(nums[mid] <= target && target <= nums[right]) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
        }

        return -1;
    }
}

当然我们也可以把nums[mid]的值与nums[right]的值比较，道理一样：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;

        while(left <= right) {
            int mid = left + (right-left)/2;

            if(nums[mid] == target) {
                return mid;
            }

            // 这里的等号一定要加
            if(nums[mid] <= nums[right]) {
                if(nums[mid] <= target && target <= nums[right]) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            } else {
                if(nums[left] <= target && target <= nums[mid]) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            }
        }

        return -1;
    }
}

[xiedaxia1hao]

第二类题：没有明确Target的题型

这一类的题比较多变，可能会要你找

• 比Target大的最小值
• 比Target小的最大值
• 满足要求的第一个值
• 不满足要求的最后一个值
• ...

在刷这类题前，我们先看看模板，在迭代退出的时候，left和right的位置：

Case 1

Array = [1,2,3,5,6], Target = 4

首先这个程序肯定返回-1。我们的模板对While Loop定义如下： while l <= r: 那么只有当l > r的时候，While Loop才会终止。 重点来了，当迭代结束后，假设Target为4， L和R的位置分别对应着两个条件： L对应的是：第一个比4大的坐标, 根据这道题的定义就是比Target大的最小值 R对应的是：最后一个比4小的坐标，根据这道题的定义就是比Target小的最大值

Case 2: L越界 [EDGE CASE]

Array = [1,2,3,5,6], Target = 7

根据我们While Loop的特性，有一个Edge的情况就是，L最大可以等于len(array)

这里可以看到，如果我们要返回array[l]，系统是会报错的，因为我们的L已经越界了，这个局限性是这套模板的小短板，当然，只要大家记住这一点，以后就可以写出相对应的Edge Case处理。

Case 3: R越界 [EDGE CASE]

类似的，R也有可能越界：

当我们把l 和 r 的位置、定义以及它们可能出现的越界情况搞清楚了之后，我们来做做题。

返回l的情况：35. Search Insert Position

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

这里我们同样可以模拟下L,R在迭代结束后的下标:

Input: [1,3,5,6], 2
Output: 1

l的下标是1， 定义是第一个满足条件的最小值。 r的下标是0，定义是最后一个不满足条件的最大值。

所以这题，我们返回l 即可，另外还要说一点，这个模板对于这道题得天独厚的好处就是，不需要考虑当target插入的下标等于len(arr)的Edge Case，因为l本身就自带这个特性。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length-1;

        while(left <= right) {
            int mid = left + (right - left)/2;

            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return left;
    }
}

返回r的情况：458. Last Position of Target (Lintcode)

给一个升序数组，找到 target 最后一次出现的位置，如果没出现过返回 -1
Example 1: 输入：nums = [1,2,2,4,5,5], target = 2 输出：2
Example 2: 输入：nums = [1,2,2,4,5,5], target = 6 输出：-1

这道题的Array里面会有重复，去重的方式就是当nums[mid] == target的时候，对left进行增值。这样就可以去掉左边重复的数。

举例：

Input: [1, 2, 2, 4, 5, 5]
target = 2, return 2

l的下标是3， 定义是第一个不满足条件的值 r的下标是2，定义是最后一个满足条件的值。

所以返回r

此题还有个特殊情况：

Input: [4]
target = 3

跑完循环后，r的下标是-1，l的下标是0。这时候r的值越界了，所以要当一个edge case处理。

public class Solution {
    public int lastPosition(int[] nums, int target) {
        if(nums == null || nums.length < 1) {
            return -1;
        }

        int left = 0, right = nums.length-1;

        while(left <= right) {
            int mid = left + (right-left)/2;

            //  nums[right] <= target < nums[left] 
            if(nums[mid] <= target) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        // EDGE CASE: nums: [4], target: 3
        if(right < 0 || nums[right] != target) {
            return -1;
        } else {
            return right;
        }

    }
}

以上两题的合体：34. Search for a Range

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。
进阶： 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

其实这题，我们可以换一个角度去考虑这个问题。

如果我们的代码中的if-else条件是这样写的：

if(a[mid] <= target)  L = mid + 1;
else   R = mid - 1;

那么while循环退出以后，L所在的位置，一定在所有 <= target 数的右边，即 target < nums[L]。 同理，R所在的位置，一定在所有 > target 数的左边，即nums[R] <= target。

最后我们就能很快的反应到：nums[R] <= target < nums[L], L = R + 1

同理，如果我们的if-else是这样写的：

if(a[mid] >= target)  R = mid - 1;
else    L = mid + 1;

那最后我们的关系就是: nums[R] < target <= nums[L], L = R + 1

知道了这层关系，下面这题我们到底是返回L还是R就很清楚了。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length < 1) {
            return new int[]{-1, -1};
        }

        int firstPos = findFirstPos(nums, target);
        int lastPos = findLastPos(nums, target);
        return new int[]{firstPos, lastPos};
    }

    public int findFirstPos(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left <= right) {
            int mid = left + (right-left)/2;

            // nums[right] < target <= nums[left]
            if(nums[mid] >= target) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }

        if(left == nums.length || nums[left] != target) {
            return -1;
        } else {
            return left;
        }
    }

    public int findLastPos(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left <= right) {
            int mid = left + (right-left)/2;

            // nums[right] <= target < nums[left]
            if(nums[mid] <= target) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        if(right < 0 || nums[right] != target) {
            return -1;
        } else {
            return right;
        }
    }
}

[xiedaxia1hao]

第三类题：没有明确Target的题型，可越界类型

这种类型的题目，用 l <= r 的模板可能会越界，我们可以填写个别的Edge Case处理，或者套用其他比如 l < r 或者 l + 1 < r 的模板解决。

162. Find Peak Element

峰值元素是指其值大于左右相邻值的元素。 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。

这题一看感觉用二分查找的方法不是很好理解。该怎么去理解比较好呢？

看了一些leetcode评论区的回复，可以这样想:

假设D代表derivative的意思。

因为题目告诉我们了nums[-1] = nums[n] = -∞，所以我们知道了 D(-1) > 0, D(n-1) < 0。如果 D(mid) < D(mid+1) ，即当前mid这个点的斜率还是向上的，说明 [mid+1, right] 区间内，肯定存在一个地方，让mid点的斜率变为0，或者<0，我们就找到了对应的peak值。

说白了，我们就是顺着一开始的 > 0的斜率走，直到我们找到一个点，斜率变为0或者小于0了，我们就找到一个peak值了。最后的结果就两种情况：

• 斜率一直都是 > 0的，直到array的最后 -> 这时候需要返回的就是最后一个元素了。
• 在循环的中间碰见一个较小的元素，斜率向下走了。 -> 这时候需要返回的是在斜率向下走之前最大的元素。

如果我们用原先的左闭右闭的模版来找峰值，mid比对的区间应该是 nums[mid + 1]，所以我们的if-else条件：

if(nums[mid] <= nums[mid+1]) {
    left = mid+1;
} else {
    right = mid-1;
}

最后left、right和peak的关系就是 nums[right] < peak <= nums[left]，因为left是往大的值靠我们返回left就好。

Example: [1, 2, 3, 1]

退出循环时，right = 1， left = 2。

但是要考虑一个特殊情况，就是当mid+1越界的时候。

Example: [1]

循环一开始，mid值为0，mid+1的值为1，这时候就会越界，所以我们碰到这种情况，直接break就行了。

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length-1;

        while(left <= right) {
            int mid = left + (right-left)/2;

            // 越界!!! 
            if(mid+1 == nums.length) break;

            // nums[right] <= peak < nums[left]            
            if(nums[mid] <= nums[mid+1]) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return left;
    }
}

那有没有什么办法可以避免越界呢？

我们可以用 l + 1 < r 的这个模版。

这个模版的终止条件是 L + 1 = R，即还剩最后两个元素的时候，就会停下来。因为这个模版left和right往中间靠的时候，不会出现+1，-1的时候，所以就不会越界。

总结一下 l + 1 < r模版的好处： 首先判断条件总是l + 1 < r， 不用担心mid = l 循环的情况。然后l = mid, r = mid, 不用担心+1-1的情况。 出来只需要多一次判断左边和右边位置的数就可以了。非常稳定。

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length-1;

        while(left + 1 < right) {
            int mid = left + (right-left)/2;

            if(nums[mid] <= nums[mid+1]) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if(nums[left] < nums[right]) {
            return right;
        } else {
            return left;
        }
    }
}

---

153. Find Minimum in Rotated Sorted Array

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

这题一开始拿来的时候，我是想通过nums[left] 和 nums[mid] 进行比较，然后进行二分的。

当nums[left] < nums[mid]的时候，left = mid+1 当nums[left] > nums[mid]的时候，right = mid-1

这样做的话，会出现一个问题：

如果这个数组没有被旋转过，就是一个sorted的数组，那当nums[left] < nums[mid]的时候，我们就把left往mid+1这方向靠了。但是这时候，数组的最小值是在index=0的位置。

所以nums[left] < nums[mid]的时候，虽然很有可能最小值处在[mid+1, right]这个区间内，但是也有可能数组的最小值就在left这个index上。所以用left和mid的关系来做这道题，不是很合适。

于是我们可以想到通过right和mid的关系来进行比较。

当nums[right] < nums[mid]的时候，最小值一定会在[mid+1, right]之间，所以我们让left = mid+1。 当nums[right] > nums[mid]的时候，最小值一定会在[left, mid-1]之间，所以我们让right=mid-1。

以下是我们用左闭右闭的模版做的，可以看见mid是有可能等于0的，因为我们要将mid和mid-1进行比较，所以有可能会出现mid-1=-1的时候，会抛异常，这时候我们可以当edge case来处理。

class Solution {
    public int findMin(int[] nums) {

        int left = 0, right = nums.length-1;

        while(left <= right) {
            int mid = left + (right-left)/2;

            if(mid != 0 && nums[mid-1] > nums[mid]) {
                return nums[mid];
            } else if(nums[right] < nums[mid]) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return nums[left];
    }
}

但是如果我们用left + 1 = right 这个模版，我们就不需要考虑edge case了。

class Solution {
    public int findMin(int[] nums) {

        int left = 0, right = nums.length-1;

        while(left + 1 < right) {
            int mid = left + (right-left)/2;

            if(nums[right] < nums[mid]) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return Math.min(nums[left], nums[right]);
    }
}

---

那如果我们想求rotated array的最大值该怎么定义if-else呢？

如果我们用上面的方法：

当nums[right] < nums[mid]的时候，让left = mid。 当nums[right] > nums[mid]的时候，让right=mid。

我们会发现，如果该数组为单调递增的时候，因为nums[right] > nums[mid]，所以我们让right=mid，最后我们把right往中间靠，正确答案就被我们靠没了。

所以正确的做法是：

• 当nums[left] < nums[mid]时，left = mid+1。
• 当nums[left] > nums[mid]时，right = mid-1。

总结一下： - 想在一个旋转后的递增数组中找到最大值时，我们让left和mid进行比较。 - 想在一个旋转后的递增数组中找到最小值时，我么让right和mid进行比较。

我们只要在脑子里想象两张图就行了，一张图是正常的rotated array，另一张图是一个普通的sorted array。然后画一下图就知道到底是让left和mid比较，还是right和mid比较了（永远记住要去比较特殊情况是不是make sense，即array是purely sorted的时候！！）

---

154. Find Minimum in Rotated Sorted Array II

这题会有一个follow up，即如果数组中存在重复的数字该怎么办。

其实就是在 nums[right] == nums[mid] 的时候，把right--。

原因是如果nums[right] == nums[mid]的值是相等的，我们没办法根据原先的逻辑去寻找最小值。但我们一定可以安全得去做的就是通过right--把搜索的范围减小 （因为nums[right] == nums[mid]，所以right--之后，不会对我们查找数组的最小值产生影响）。

class Solution {
    public int findMin(int[] nums) {

        int left = 0, right = nums.length-1;

        while(left + 1 < right) {
            int mid = left + (right-left)/2;
            if(nums[right] > nums[mid]) {
                right = mid;
            } else if(nums[right] < nums[mid]){
                left = mid;
            } else {
                right--;
            }
        }

        if(nums[left] < nums[right]) {
            return nums[left];
        } else {
            return nums[right];
        }
    }
}

[xiedaxia1hao]

MISC.

这个板块来讲一些Grokking. 上有意思的题目。

如何对于一个unknown size的array进行二分查找

Grokking. Search in a Sorted Infinite Array

Given an infinite sorted array (or an array with unknown size), find if a given number ‘key’ is present in the array. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.
Since it is not possible to define an array with infinite (unknown) size, you will be provided with an interface ArrayReader to read elements of the array. ArrayReader.get(index) will return the number at index; if the array’s size is smaller than the index, it will return Integer.MAX_VALUE.

这题和上面的题都不一样，因为我们不知道array的长度，自然就没有办法直接的做二分查找。

所以这题我们要先找到我们要找的目标所在的区间，然后再在这个区间内进行二分查找。

那这个区间怎么找呢？我们可以刚开始把这个区间的长度设置成1，然后把这个区间进行指数型增长，知道我们的key存在于这个区间内。如图：

class ArrayReader {
  int[] arr;

  ArrayReader(int[] arr) {
    this.arr = arr;
  }

  public int get(int index) {
    if (index >= arr.length)
      return Integer.MAX_VALUE;
    return arr[index];
  }
}

class SearchInfiniteSortedArray {

  public static int search(ArrayReader reader, int key) {
    // find the proper bounds first
    int start = 0, end = 1;
    while (reader.get(end) < key) {
      int newStart = end + 1;
      end += (end - start + 1) * 2; // increase to double the bounds size
      start = newStart;
    }
    return binarySearch(reader, key, start, end);
  }

  private static int binarySearch(ArrayReader reader, int key, int start, int end) {
    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (key < reader.get(mid)) {
        end = mid - 1;
      } else if (key > reader.get(mid)) {
        start = mid + 1;
      } else { // found the key
        return mid;
      }
    }

    return -1;
  }

  public static void main(String[] args) {
    ArrayReader reader = new ArrayReader(new int[] { 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 });
    System.out.println(SearchInfiniteSortedArray.search(reader, 16));
    System.out.println(SearchInfiniteSortedArray.search(reader, 11));
    reader = new ArrayReader(new int[] { 1, 3, 8, 10, 15 });
    System.out.println(SearchInfiniteSortedArray.search(reader, 15));
    System.out.println(SearchInfiniteSortedArray.search(reader, 200));
  }
}

---

Grokking. Bitonic Array Maximum: 从双调数组中找到最大的数字

Find the maximum value in a given Bitonic array. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array arr[i] != arr[i+1].

这题和162. Find Peak Element的思路是一样的，虽然Find Peak Element这道题里面有多个peak，这道题里面只有一个peak，原理还是类似的。

class MaxInBitonicArray {

  public static int findMax(int[] arr) {
    int left = 0, right = arr.length-1;

    while(left + 1 < right) {
      int mid = left +(right-left)/2;
      if(arr[mid] <= arr[mid+1]) {
        left = mid;
      } else {
        right = mid;
      }
    }

    if(arr[left] < arr[right]) {
      return arr[right];
    } else {
      return arr[left];
    }
  }

  public static void main(String[] args) {
    System.out.println(MaxInBitonicArray.findMax(new int[] { 1, 3, 8, 12, 4, 2 }));
    System.out.println(MaxInBitonicArray.findMax(new int[] { 3, 8, 3, 1 }));
    System.out.println(MaxInBitonicArray.findMax(new int[] { 1, 3, 8, 12 }));
    System.out.println(MaxInBitonicArray.findMax(new int[] { 10, 9, 8 }));
  }
}

---

Grokking. Search Bitonic Array: 从双调数组中找到target数字

Given a Bitonic array, find if a given ‘key’ is present in it. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array arr[i] != arr[i+1].
Write a function to return the index of the ‘key’. If the ‘key’ is not present, return -1.

这道题和33. Search in Rotated Sorted Array并不是完全一样的。

Rotated Sorted Array是由sorted的数组通过旋转得到的，也就是说，在最高点peak两边的子数组都是分别递增的，且数组中的最高点的右边的所有数字，一定小于数组中最高点左边的所有数字。

而Bitonic Array就没有这种讲究了，整个数组是先递增，再递减的，且最高点左边的数字和最高点右边的数字分布具有随机性。

所以这题我们的思路是：

• 先通过上一题的思路找到peak值所在的maxIndex。
• 把array通过maxIndex分成两份：[0: maxIndex] & [maxIndex+1, array.length-1]。
• 对其中一个部分的array进行binary search，如果没找到的话，就换另一边。

还要注意的是，这题分出来的两个array，分别是递增和递减的，所以写binary search的时候也要注意写成order-agnostic版本的binary search。

所以这道题是两道题的合并：

Order-Agnostic Binary Search & Bitonic Array Maximum

class SearchBitonicArray {

  public static int search(int[] arr, int key) {
    int maxIndex = findMaxIndex(arr);
    int resIndex = binarySearch(arr, 0, maxIndex, key);
    if(resIndex == -1) {
      resIndex = binarySearch(arr, maxIndex+1, arr.length-1, key);
    }
    return resIndex;
  }

  public static int binarySearch(int[] arr, int left, int right, int key) {
    boolean isAscending = arr[left] < arr[right];

    while(left <= right) {
      int mid = left + (right-left)/2;
      if(arr[mid] == key) return mid;

      if(isAscending) {
        if(arr[mid] < key) left = mid+1;
        else right = mid-1;
      } else {
        if(arr[mid] < key) right = mid-1;
        else left = mid+1;
      }
    }

    return -1;
  }

  public static int findMaxIndex(int[] arr) {
    int left = 0, right = arr.length-1;
    while(left + 1 < right) {
      int mid = left + (right-left)/2;
      if(arr[mid] <= arr[mid+1]) {
        left = mid;
      } else {
        right = mid;
      }
    }

    if(arr[left] > arr[right]) {
      return left;
    } else {
      return right;
    }
  }

  public static void main(String[] args) {
    System.out.println(SearchBitonicArray.search(new int[] { 1, 3, 8, 4, 3 }, 4));
    System.out.println(SearchBitonicArray.search(new int[] { 3, 8, 3, 1 }, 8));
    System.out.println(SearchBitonicArray.search(new int[] { 1, 3, 8, 12 }, 12));
    System.out.println(SearchBitonicArray.search(new int[] { 10, 9, 8 }, 10));
  }
}

---

Grokking. Rotation Count

Given an array of numbers which is sorted in ascending order and is rotated ‘k’ times around a pivot, find ‘k’. You can assume that the array does not have any duplicates.

这题如果把153. Find Minimum in Rotated Sorted Array练熟的话，这题就不难了。

我们先找到这个array的peak值对应的index，然后return index+1即可，如果该index == arr.length-1, 说明是sorted的，直接return 0。

class RotationCountOfRotatedArray {

  public static int findPeakIndex(int[] arr) {
    int left = 0, right = arr.length-1;
    while(left + 1 < right) {
      int mid = left + (right-left)/2;
      if(arr[left] > arr[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    if(arr[left] < arr[right]) {
      return right;
    } else {
      return left;
    }
  }
  public static int countRotations(int[] arr) {
    int peakIndex = findPeakIndex(arr);
    return peakIndex == arr.length-1 ? 0 : peakIndex+1;
  }

  public static void main(String[] args) {
    System.out.println(RotationCountOfRotatedArray.countRotations(new int[] { 10, 15, 1, 3, 8 }));
    System.out.println(RotationCountOfRotatedArray.countRotations(new int[] { 4, 5, 7, 9, 10, -1, 2 }));
    System.out.println(RotationCountOfRotatedArray.countRotations(new int[] { 1, 3, 8, 10 }));
  }
}