使用二分的情况:
1.遍历时间复杂度太大
2.要从数组中找到一个元素
460. Find K Closest Elements(找到最后一个 < target 的位置)
https://www.lintcode.com/problem/find-k-closest-elements/description?_from=ladder&&fromId=1
思路:
1. 找到最后一个 < target 的位置,然后从这个位置开始用两根指针向两边走 ----> 先从一个排好序的数组中查找一个目标元素 ---> 二分法 。
2. 二分法,目标一定在 [left, right] 之间。
public class Solution { /** * @param A: an integer array * @param target: An integer * @param k: An integer * @return: an integer array */ public int[] kClosestNumbers(int[] A, int target, int k) { // write your code here if(A == null || A.length == 0) return null; int[] result = new int[k]; //binary search to find lower closet to target int left = 0; int right = A.length - 1; while(left + 1 < right) { int mid = left + (right - left) / 2; if(A[mid] < target) { left = mid; } else { right = mid; } } if(A[right] < target) left = right; //sort in ascending order by number right = left + 1; for(int i = 0; i < k; i++) { if(isLeftCloser(A, left, right, target)) { result[i] = A[left]; left--; } else { result[i] = A[right]; right++; } } return result; } public boolean isLeftCloser(int[] A, int left, int right, int target) { if(left < 0) { return false; } if(right >= A.length) { return true; } if(target - A[left] != A[right] - target) { return target - A[left] < A[right] - target; } return true; } }
460. Search in a Big Sorted Array(找到第一个不小于 target 的元素)
https://www.lintcode.com/problem/search-in-a-big-sorted-array/description?_from=ladder&&fromId=1
方法一:二分法
1. 通过倍增右指针,找到第一个不小于 target 的元素。目的:确定 target 的范围,target 的下标一定在 left 和 right 之间。------> 二分法
2.注意:越界访问是没有关系的,因为这个 ArrayReader 在越界访问时,返回 INT_MAX,一定不小于 targe,而即使是返回 -1 之类的数值,我们也可以加一个判断搞定。
/** * Definition of ArrayReader: * * public class ArrayReader { * public int get(int index) { * // return the number on given index, * // return 2147483647 if the index is invalid. * } * }; */ public class Solution { /* * @param reader: An instance of ArrayReader. * @param target: An integer * @return: An integer which is the first index of target. */ public int searchBigSortedArray(ArrayReader reader, int target) { // write your code here int left = 0; int right = 1; while(reader.get(right) < target) { right *= 2; } while(left + 1 < right) { int mid = left + (right - left) / 2; if(reader.get(mid) < target) { left = mid; } else { right = mid; } } if(reader.get(left) == target) { return left; } else if(reader.get(right) == target) { return right; } return -1; } }
428. Pow(x, n)
https://www.lintcode.com/problem/powx-n/description?_from=ladder&&fromId=1
这道题如果用for循环把x乘以n次的话,会超时。
该如何降低时间复杂度呢?
二分法:把指数二分
public class Solution { /** * @param x: the base number * @param n: the power number * @return: the result */ public double myPow(double x, int n) { // write your code here boolean isNegative = false; if(n < 0) { isNegative = true; n = -(n + 1); x = 1 / x; } double result = 1, temp = x; while(n != 0) { if(n % 2 != 0) { result *= temp; } temp *= temp; n /= 2; } if(isNegative) { result *= x; } return result; } }