算法：贪心算法与二分查找-理论与实战
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_43126117/article/details/100596610
贪心算法
概念：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
例子：兑换零钱
对于兑换36元的零钱，也就是找36的子结构最优解，贪心算法会按照20>10>5>1这个方式进行。
我们把金额和面值都改一下，面值为10 6 1 ，兑换金额为13 。
按照贪心算法，会选择第一种，我们知道第二种才是最优的。
但是我们看问题更多的是从整体到细节，局部的最优解组合起来成为整体的最优解，这样的情况是很少的，所以也意味着贪心算法的适用情况是很少的。因为贪心算法一般没有测试所有可能的解。贪心法容易过早做决定，因而没法达到最佳解。
贪⼼算法与动态规划的不同在于它对每个⼦问题的解决⽅案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进⾏选择，有回退功能。
leetcode122:买卖股票的最佳时机 II
题解：一天可以多次买卖，先卖再卖，计算怎么才更赚钱，其实也就是搜索问题，找出所有的解再返回最大值。
我们也可以用贪心算法来做，把这个数组买卖的过程分为局部情况，更后序元素比较大小，后面的大，那么就卖出，后序的要是小，那就
不买。找到局部最有利的结果，那么组合起来就是全局最优解。
public int maxProfit(int[] prices) {
int count = 0;
for (int i = 0; i < prices.length-1; i++) {
if (prices[i] < prices[i + 1]) {
count = prices[i + 1] - prices[i] + count;
}
}
return count;
}二分查找
概念：一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找算法有一个使用前提。
1.数组必须单调递增或者单调递减
2.数组必须存在上下界
3.能够通过索引快速访问
leetcode:求69X的平方根
题解：就是求平方根，一种比较简单的办法就是二分算法，为什么呢？这道题有二分算法的的使用前提吗？
这个平方根的可能解是由零开始递增的直到x ，那么存在上下界，也具有快速访问数字的情况。
public int mySqrt(int x) {
if (x == 0 || x == 1) return x;
int left = 0;
int right = x;
int res = 0;
while (left <= right) {
int mid = left + (right - left) / 2; //直接平均可能會溢位，所以用此算法类似(left+right)/2
if (mid < x / mid) {
left = mid + 1;
res = mid ;
} else if (mid > x / mid) {
right = mid - 1;
} else if (mid <= x / mid && (mid + 1) >= x / mid) //mid*mid=x
return mid;
}
return res;
}上面的就是二分查找算法的迭代写法，类似通用写法。
二分查找的递归通用写法
public static int binarySearch(int[] arr, int start, int end, int hkey){
if (start > end)
return -1;
int mid = start + (end - start)/2; //防止溢位
if (arr[mid] > hkey)
return binarySearch(arr, start, mid - 1, hkey);
if (arr[mid] < hkey)
return binarySearch(arr, mid + 1, end, hkey);
return mid;
}