分治法
1.二分搜索（算法时间复杂度O(log n)）
输出：如果x=A[j],则输出j，否则输出0.
1.binarysearch(1,n)
过程：binarysearch(low,high) 1.if low>high then return 0
2.else
3. mid←(low+high)/2
4. if x=A[mid] then return mid
5. else if x<A[mid] then return binarysearch(low,mid-1)
6. else return binarysearch(mid+1,high)
7.end if
Leetcode NO33 搜索旋转数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。
class Solution {
public int search(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
// 当[0,mid]有序时,向后规约条件
if (nums[0] <= nums[mid] && (target > nums[mid] || target < nums[0])) {
lo = mid + 1;
// 当[0,mid]发生旋转时，向后规约条件
} else if (target > nums[mid] && target < nums[0]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo == hi && nums[lo] == target ? lo : -1;
}
}LeetCode NO53 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
这个题目其实不用分治法做会很简单：
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
}但是复盘的时候肯定要用分治法做一做的。
public class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
return maxSubArraySum(nums, 0, len - 1);
}
private int maxCrossingSum(int[] nums, int left, int mid, int right) {
// 一定会包含 nums[mid] 这个元素
int sum = 0;
int leftSum = Integer.MIN_VALUE;
// 左半边包含 nums[mid] 元素，最多可以到什么地方
// 走到最边界，看看最值是什么
// 计算以 mid 结尾的最大的子数组的和
for (int i = mid; i >= left; i--) {
sum += nums[i];
if (sum > leftSum) {
leftSum = sum;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
// 右半边不包含 nums[mid] 元素，最多可以到什么地方
// 计算以 mid+1 开始的最大的子数组的和
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
if (sum > rightSum) {
rightSum = sum;
}
}
return leftSum + rightSum;
}
private int maxSubArraySum(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = (left + right) >>> 1;
return max3(maxSubArraySum(nums, left, mid),maxSubArraySum(nums, mid + 1, right),maxCrossingSum(nums, left, mid, right));
}
private int max3(int num1, int num2, int num3) {
return Math.max(num1, Math.max(num2, num3));
}
}