二分查找又称折半查找，实际操作时，在排好序的队列中，每次取中间位置值与目标值对比，由于已经排序，无论对比结果如何都可以删除一半的搜索空间，除非一次命中，因此其时间复杂度为O(log2n)。
leetcode中列出了二分查找中常用的三种形式：Template I、Template II、Template III
Template I
必找到型，要么找到，要么找不到，开区间
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
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 -1;
}
Template II
逼近型，寻找过程中找到即找到，找不到则在最后的逼近位置查看，左开右闭区间
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;//右脚在外
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;//右脚踩点，即右闭区间
}
}
if (left != nums.length && nums[left] == target) return left;
return -1;
}
Template III
逼近型，闭区间
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right) {//两脚汇合，中间有距离
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;//左脚踩点，即左闭区间
} else {
right = mid;//右脚踩点，即右闭区间
}
}
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
Sqrt(x)
求x的平方根，编码时都是使用库函数，拿到这题时真懵了。
一个正整数的平方根必定在[1,x)，如1，除1外其他正整数区间为(1,x)，当然0的平方根还是0（如果左脚为1，右脚为0，二分查找的两脚在起始时就交叉了）。通过分析，题目变成了在[1,x)中找平方为x的数
private int mySqrt(int x) {
int left = 1;
int right = x;
while (left <= right) {
int mid = left + (right - left) / 2;//防止越界
if (mid == x / mid) {
return mid;
}
if (mid < x / mid) {//如果mid足够大，mid * mid则会越界，所以通过x / mid来防止越界
left = mid + 1;//1的特例已经过了，所以左脚要迈进而不是踩点
} else {
right = mid - 1;
}
}
if (left > x / left) {//当x不能完全开平方时，取整数位
return left - 1;
} else {
return left;
}
}
Search in Rotated Sorted Array
将升序的数组，按某枢轴旋转形成新的数组，在新的数组中查找目标。
[0,1,2,4,5,6,7] 移动后 [4,5,6,7,0,1,2]
这是一个变相的二分查找，数组并未排好序，首要任务就是将其重新排序，再用二分法查找。
既然数组是旋转而来，再将它旋转就会回到有序数组。观察数组，轴点左侧、右侧的子数组各为升序，所以最小值所在的位置即为轴心。
private int search(int[] nums, int target) {
int pivot = getPivot(nums);//获取轴心位置
int len = nums.length;
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;//排序数组的中间位置
int realPosition = (mid + pivot) % len;//偏移后中间位置，在未排序数组中的实际位置
if (target == nums[realPosition]) return realPosition;
if (target > nums[realPosition]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
//左侧未排序的数组各项都大于右侧未排序数组项
private int getPivot(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {//mid在右侧数组
right = mid;
} else {//mid在左侧数组
left = mid + 1;
}
}
return left;
}
Find Peak Element
在数组中大于左右项的称为Peak，找出其位置，多个Peak时，返回任意一项。
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
private int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left <= right) {
if (left == right)
return left;
int mid = (left + right) / 2;
if (nums[mid] < nums[mid + 1])//自己小于右的话，peak在右边,左脚迈进
left = mid + 1;
else//自己大于右边，peak可能是自己也可能在左边，右脚踩点
right = mid;
}
return -1;
}
Search for a Range
给定升序数组，但数组内有重复项，求目标项的位置范围。
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
两种解法都是采用二分法，时间复杂度为O(log2n)，非二分法的在文末的GitHub上，此方法时间复杂度不稳定。
解法一
首先查找到目标项的一个位置，从此位置向左向右继续查找
public int[] searchRange(int[] nums, int target) {
if(nums==null||nums.length==0){
return new int[]{-1,-1};
}
int left,right;
left=right=searchPoint(nums,0,nums.length-1,target);//查找任意位置的target
int temp;
while((temp=searchPoint(nums,0,left-1,target))!=-1){//从找到的位置向左查找
if(left!=temp){
left=temp;
}else{
break;//找不到就终止，说明已经出了要找的范围
}
}
while((temp=searchPoint(nums,right+1,nums.length-1,target))!=-1){//从找到的位置向右查找
if(right!=temp){
right=temp;
}else{
break;
}
}
return new int[]{left,right};
}
//Template I
private int searchPoint(int[] nums,int left,int right,int target){
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}
if(nums[mid]>target){
right=mid-1;
}else{
left=mid+1;
}
}
return -1;
}
解法二
利用Template III闭合区间的性质，依次找到左右点。
private int[] searchRange(int[] nums, int target) {
int[] res = {-1, -1};//默认结果
if (nums == null || nums.length == 0) return res;//空
int start = 0, end = nums.length - 1;
int mid;
while (start + 1 < end) {//Template III求目标项，
mid = start + (end - start) / 2;
if (nums[mid] < target) start = mid;//start位置项不等于target
else end = mid;//end位置项等于target
}
//得到的start和end必定是(,]左开右闭区间，是最终结果范围的左边
if (nums[start] == target) res[0] = start;
else if (nums[end] == target) res[0] = end;
else return res;
//复位
start = 0;
end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] > target) end = mid;//end位置项不等于target
else start = mid;//start位置项等于target
}
//得到的start和end必定是[,)左闭右开区间，是最终结果范围的右边
if (nums[end] == target) res[1] = end;
else if (nums[start] == target) res[1] = start;
else return res;
return res;
}
Find K Closest Elements
给一升序数组、目标值x和要求的结果数量k。求在数组内与目标值x，相差绝对值最少的k个项，差相同时取小的项。
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
做k大小的滑动窗口，通过比较窗口两边差值的大小，将窗口位置固定
private List<Integer> findClosestElements(int[] nums, int k, int x) {
int left = 0;
int right = nums.length - k;
while (left < right) {
int mid = left + (right - left) / 2;
if (Math.abs(nums[mid] - x) > Math.abs(nums[mid + k] - x)) {
left = mid + 1;
} else {
right = mid;
}
}
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i < k; i++) {
res.add(nums[left + i]);
}
return res;
}
Pow(x, n)
求x的n次方
任何数的0次方都为1，可以通过递归求1次方，2次方，4次方....趋近n，注意n的奇偶还有正负
public double myPow(double x, int n) {
double res=pow(x,n);
if(n<0){//先求正数，后求负数
res=1/res;
}
return res;
}
private double pow(double x, int n) {//递归
if (n == 0) return 1;//0次方
double half = pow(x, n / 2);//此处除以2会损失精度
double res;
if (n % 2 == 0) {//将损失的精度补回来
res = half * half;
} else {
res = half * half * x;
}
return res;
}
Valid Perfect Square
判断是否为完全平方数
类似前面的Sqrt(x)
private boolean isPerfectSquare(int num) {
int left = 1;
int right = num;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid * mid == num) {//忽略越界，提高准确度
return true;
}
if (mid < num / mid) {//防止越界
left = mid + 1;
} else {
right = mid - 1;
}
}
return left * left == num;
}
Find Smallest Letter Greater Than Target
在给定排序字符串中，查找大于target的一项
private char nextGreatestLetter(char[] letters, char target) {
int left = 0;
int right = letters.length-1;
while (left < right) {
int mid = left + (right - left) / 2;
if (target >= letters[mid]) {//查找target的后一项
left = mid+1;
} else {
right = mid;
}
}
if (target >= letters[left]) {
int pos = left + 1;
if (pos > letters.length - 1) {//如果target是最后一项
pos = 0;
}
return letters[pos];
} else {
return letters[left];
}
}
Find Minimum in Rotated Sorted Array II
将升序数组按某枢轴旋转，查找最小项，但数组内有重复项。
类似Search in Rotated Sorted Array中查找轴心
private int findMin(int[] nums) {
int left=0;
int right=nums.length-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]==nums[right]){//移除一重复项
right--;
continue;
}
if(nums[mid]>nums[right]){
left=mid+1;
}else{
right=mid;
}
}
return nums[left];
}
Two Sum II
是否在数组中存在任意两项和等于target
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
target减一项得差，查找差是否存在于数组中
private int[] twoSum(int[] numbers, int target) {
int index1, index2;
for (int i = 0; i < numbers.length - 1; i++) {
if (target - numbers[i] < numbers[i]) {//要找的数，比当前位置数还小，没必要向后找
break;
}
int temp = search(numbers, i + 1, numbers.length - 1, target - numbers[i]);
if (temp != -1) {
index1 = i + 1;
index2 = temp + 1;
return new int[]{index1, index2};
}
}
return new int[]{-1, -1};
}
private int search(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Find the Duplicate Number
有一数组，共n+1项，每项的取值范围[1,n]，则数组中最少有一重复项（不验证了），假设只有一项重复，求此项。
二分法
算出取值范围[1,n]的中间值mid，遍历数组统计小于mid值的个数，如果个数大于mid，则重复值在[1,mid]中。因为只有一个重复值不在mid的左边就是右边，在哪边哪边的个数就多。
private int findDuplicate(int[] nums) {
int left = 1;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int count = 0;
for (int num : nums) {
if (num <= mid) {
count++;
}
}
if (mid < count) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
追逐法
数组好比一条直线，当有重复项是便会有连接，于是就形成了直线切圆的图形。
现有两指针fast、slow，fast每次走2步slow每次走1步，它们前进的最终命运都是在圆内转圈。
设：M点为fast、slow的交汇点，C为圆周长
则交汇时有：slow行走了L1 + L2，fast行走了L1+ n * C + L2
等式有：2 * (L1+L2) = L1 + L2 + n * C
等式移动：L1 + L2 = n * C
等式移动：L1 = (n - 1)* C + (C - L2)
即：HE=ME+n*C（逆时针）
当fast、slow交汇时，slow速度不变还是继续向前，而fast将其放到H并设置速度与slow相同，当fast、slow再次交汇时一定在E点即重复点。
private int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
参考：http://bookshadow.com/weblog/2015/07/10/leetcode-linked-list-cycle-ii/
Median of Two Sorted Arrays
给两个有序数组，求数组中的中间项，数组项为偶数时则是中间两项的平均值。
nums1 = [1，3]
nums2 = [2]The median is 2.0
nums1 = [1，2]
nums2 = [3，4]The median is (2 + 3)/2 = 2.5
有数组nums1[1，3，8，9，15]长度x为5，nums2[7，11，18，19，21，25]长度y为6，求它们的中间值。
两数组合并有[1，3，7，8，9，11，15，18，19，21，25]长度为11，中间值在位置（m + n）/ 2 = 5为11。
因为nums1、nums2都是有序数组，将它们从中一分为二成Left、Right，但并不是平均分需要nums1的切分点partitionX加nums2的切分点partitionY和等于合并数组的一半（partitionX + partitionY = (x + y + 1) / 2），nums1在partitionX=2，nums2在partitionY=3切分有：
| * | Left | Right |
|---|---|---|
| nums1 | 1、3 | 8、9、15 |
| nums2 | 7、11、18、19 | 21、25 |
Left组成数组[1，3，7，11，18，19]内的项并不全部小于Right组成的数组[8，9，15，21，25]，需要移动数组内的项使Left各项小于Right各项。
通过边界点来判读，交叉比较：3 < 21 but 19 < 8 ？
所以nums2的19项需要移到Right，联动反应nums1的8项需要移到Left
| * | Left | Right |
|---|---|---|
| nums1 | 1、3、8 | 9、15 |
| nums2 | 7、11、18 | 19、21、25 |
交叉比较：8 < 19 but 18 < 9 ？
所以nums2的18项需要移到Right，联动反应nums1的9项需要移到Left
| * | Left | Right |
|---|---|---|
| nums1 | 1、3、8、9 | 15 |
| nums2 | 7、11 | 18、19、21、25 |
交叉比较：9 < 18 and 11 < 15
取Left的Max、Right的Min
当x + y为奇数时取LeftMax，偶数时取LeftMax和RightMin的均值
由于x + y为奇数所以结果为LeftMax = 11
private double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int x = nums1.length;
int y = nums2.length;
int low = 0;
int high = x;
while (low <= high) {
int partitionX = low + (high - low) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;
int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((x + y) % 2 == 0) {
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
} else {
return Math.max(maxLeftX, maxLeftY);
}
} else if (maxLeftX > minRightY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
return -1;
}
Find K-th Smallest Pair Distance
数组内各项组队求差，求第K项小的差值。
Input:
nums = [1,3,1]
k = 1
Output: 0
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.
逆向思维，将差值排序，求第K项。
private int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
// 由于已排序，任意项与其后多项的差为增序
// 距离数组下表，二分法逼近所求第K项
int left = 0;//组队的最小距离
int right = nums[nums.length - 1] - nums[0];//组队的最大距离
while (left < right) {
int mid = left + (right - left) / 2;//组队的中间距离，可以不存在
int cnt = 0;//小于组队的中间距离的，组队的个数
for (int i = 0, j = 0; i < nums.length; i++) {
while (j < nums.length && (nums[j] - nums[i]) <= mid) j++;
cnt += j - i - 1;//每次会有i=j,重复了一次
}
if (cnt < k) {//组对数小于k,说明小于此left、right的组队的中间距离的组队数小于K，需要将组队的中间距离加大
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
Split Array Largest Sum
给一数组nums和整数m，将数组分成m个非空子数组，使子数组内各项之和最小
Input:
nums = [7,2,5,10,8]
m = 2Output:
18Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.
逆向思维，数组各项和可能出现的最大与最小值可知，（m=1时，存在最大值为nums各项之和；m=nums.length时，存在最小值为nums内的最大项值），通过最大最小值使用二分法求得m个子数组时最小值为多少。
private int splitArray(int[] nums, int m) {
int sum = 0;//m=1
int max = 0;//m=nums.length
for (int num : nums) {
sum += num;
max = num > max ? num : max;
}
return binary(nums, m, max, sum);
}
private int binary(int[] nums, int m, int left, int right) {
while (left < right) {
int mid = left + (right - left) / 2;//可能出现的子数组各项和
if (valid(nums, m, mid)) {//此和是否符合条件
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean valid(int[] nums, int m, int mid) {
int sum = 0;
int count = 1;
for (int num : nums) {//逐项相加
sum += num;
if (sum > mid) {//符合项数和的条件
count++;//项数+
sum = num;
if (count > m) {//符合项数和条件，但不符合项数条件
return false;
}
}
}
return true;
}
