二分搜索binary search和贪婪算法

二分搜索binary search

定义：二分搜索也称折半搜索，是一种在有序数组中查找某一特定元素的搜索算法。

运用前提：必须是排好序的。
输入并不一定是数组，也可能是给定一个区间和终止的位置。

优点:、

• 二分搜索也叫对数搜索，其时间复杂度为O(log n),是一种非常高效的搜索。

缺点：

• 要求待查找的数组或者区间是排好序的
• 如果要求对数组进行动态删除和插入操作，并完成查找，平均复杂度会变为O(n)

1. 采取自平衡二叉查找树
2. 可在O(nlogn)的时间内用给定的数据构建出一颗二叉查找树。
3. 可在O(logn)的时间内对数据进行搜索
4. 可在O(logn)的时间内完成插入和删除的操作

当：输入的数组或区间是有序的，且不会常变动，要求从中找出一个满足条件的元素->二分搜索binary

基本结题模板
递归：
  优点是简洁
  缺点是执行消耗大
  

  int binary_search(int nums[],int target,int low,int high)
  {
     if(low>high) return -1;
     int middle = (low+high)/2;
     if(nums[middle]== target)
     return middle;
     
     if(nums[middle]> target)
     {
        return binary_search(nums,target,low,middle-1);
     }else
     {
        return binary_search(nums,target,middle+1,high);
     }
  }

  三个关键点

• 计算middle下标时，不能简单地用(low+high)/2 这样可能会导致溢出
• 取左半边[low,middle-1]
• 取右半边[middle+1，high] 
• 我们确定了middle点是不是我们要找的点，
• 因此没有必要再把它加入左右半边了
• 对于一个长度为奇数的数组，按照low+(high-low)/2来计算的话，middle就是正中间的那位。
• 对于偶数个的数组，middle就是正中间那个

核心思想：

1. 确定搜索的范围和区间
2. 取中间的数判断是否满足条件
3. 如果不满住，判断应该往那个半边继续进行搜索。

 int binary_search(int nums[],int target,int low,int high)
 {
     while(low<=high)
     {
        int middle = low+(high-low)/2;
        if(nums[middle]== target)
        return middle;
        
        if(nums[middle]>target)
        {
            high = middle-1;
        }else
        {
            low = middle+1;
        }
     }
     return -1;
 }

找确定的边界

贪婪算法：  

Greedy 总是做出在当前看来最好的选择

不从整体的角度去考虑，仅对局部的最优解感兴趣
什么问题适用贪婪算法？
只有当哪些局部最优策略能产生全局最优策略的时候。

背包问题：
有三种不同的贪婪策略
1、选取价值最大的物品
2、选取重量最小的物品
3、选取价值/重量比最大的物品

贪婪物品有   A  B  C
重量分别是： 25,10,10
价值分别是：100,80,80