算法第四版- 3.1

• • **算法第四版- 3.1**
• 1.二分查找
• • 1)LC704二分查找
  • 2)LC744二分查找
  • 3)LC33搜索旋转排序数组
  • 4）搜索旋转数组进阶
• 2.跳表

关于二分查找的漫画
代码如下：

找到的话，就返回索引；找不到，就返回-1

class Solution {
public:
    int search(vector& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<=r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]>target) r=mid-1;
            else if(nums[mid] 
2)LC744二分查找 
在字符串中找比target字符大的字符
 如果找不到，返回第一个字符。（因为二分查找最后两个指针都会落在最开始了）
 当然我们也知道，如果你最后找到了，那么答案的索引是左指针L
 
class Solution {
public:
    char nextGreatestLetter(vector& letters, char target) {
        int len = letters.size();
        int l = 0;
        int r = len - 1;
        while (l <= r)
        {
            int mid = l + (r - l) / 2;
            if (target < letters[mid])
                r = mid - 1;
            else
                l = mid + 1;
        }
        return letters[l % len];

    }
};
 
思考旋转有序数组：
 
3)LC33搜索旋转排序数组 
输入：nums = [4,5,6,7,0,1,2], target = 0
 输出：4
 输入：nums = [4,5,6,7,0,1,2], target = 3
 输出：-1
 那肯定也是用二分查找。
 热评：
 
 代码如下：
 
class Solution {
public:
    int search(vector& nums, int target) {
        int len=nums.size();
        int left=0,right=len-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid] 
4）搜索旋转数组进阶 
好几种题型
 这个讲的非常好，循序渐进。
 
2.跳表 
跳表就是对于链表的二分查找
 关于跳表的漫画
 跳表的析构比较难搞，导致删除节点比较难写。
 浏览别人的博客后发现C++写的基本都是析构写的不是很好。java本身的内存回收倒是很不错。不知道C++的智能指针能不能解决这个问题，后话吧。
 记得刷题见到过一句话：“有序必二分”
 手头有魏先生的《小灰算法2》，所以借鉴了很多漫画。