Binary Search in Value

用法

Binary Search in Value的问题一般不像Binary Search in Sorted Array那样容易辨认出来。因为Binary Search in Sorted Array的问题如果给定sorted array或者我们可以去sort array，思路会比较明显。但是Binary Search in Value的问题还是可以辨别出特征的。主要特征有两点：

• 暴力解法的时间复杂度是O(n)，这个和Binary Search in Sorted Array一样，因为做的是point query，所以最坏也就是把整个区间扫一遍，时间复杂度是O(n)，如果暴力法时间复杂度很高才可以，那很有可能这道题不能用binary search。

• 我们做的是point query，找的是那个分割线。这个分割线可以让我们每次把搜索的范围减半。

题目

求sqrt

• Leetcode 367. Valid Perfect Square (先用binary search求sqrt，然后乘回来)
• Leetcode 374. Guess Number Higher or Lower
• Leetcode 400. Nth Digit
• Leetcode 69. Sqrt(x)
• Leetcode 410. Split Array Largest Sum