時(shí)間復(fù)雜度
- O(1) 極少
- O(logn) 幾乎都是二分法
- O(√n) 幾乎是分解質(zhì)因數(shù)
- O(n) 高頻
- O(nlogn) 一般都可能要排序
- O(n^2) 數(shù)組夫晌，枚舉您朽，動(dòng)態(tài)規(guī)劃
- O(n^3) 數(shù)組嘹履，枚舉，動(dòng)態(tài)規(guī)劃
- O(2^n) 與組合有關(guān)的搜索
- O(n!) 與排列有關(guān)的搜索
遞歸與非遞歸
- 不用遞歸是否造成實(shí)現(xiàn)的復(fù)雜
- 遞歸的深度是否很深
二分法通用模板
- 可擴(kuò)展于尋找target第一次出現(xiàn)的位置笛辟，最后一次出現(xiàn)的位置
public class BinarySearch {
/**
* @param nums: The integer array sorted in ascending order.
* @param target: Target to find.
* @return: The position of target.
*/
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return nums[mid];
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] == target) return start;
else if (nums[end] == target) return end;
else return -1;
}
}
public int runBinarySearchIteratively(
int[] sortedArray, int key, int low, int high) {
int index = Integer.MAX_VALUE;
while (low <= high) {
int mid = (low + high) / 2;
if (sortedArray[mid] < key) {
low = mid + 1;
} else if (sortedArray[mid] > key) {
high = mid - 1;
} else if (sortedArray[mid] == key) {
index = mid;
break;
}
}
return index;
}
public int runBinarySearchRecursively(
int[] sortedArray, int key, int low, int high) {
int middle = (low + high) / 2;
if (high < low) {
return -1;
}
if (key == sortedArray[middle]) {
return middle;
} else if (key < sortedArray[middle]) {
return runBinarySearchRecursively(
sortedArray, key, low, middle - 1);
} else {
return runBinarySearchRecursively(
sortedArray, key, middle + 1, high);
}
}
