Leetcode 702. 搜索长度未知的有序数组（DAY 178）---- 二分查找学习期

左手的ㄟ右手 2022-09-13 14:28 150阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

/** * // This is the ArrayReader's API interface. * // You should not implement it, or speculate about its implementation * class ArrayReader { * public: * int get(int index); * }; */
    
    class Solution { 
    public:
        int search(const ArrayReader& reader, int target) { 
            int pos_left = 0,pos_right = 20000;
            while(pos_left < pos_right)
            { 
                int mid = (pos_left + pos_right) / 2;
                if(reader.get(mid) == INT_MAX) pos_right = mid;
                else
                { 
                    if(reader.get(mid) == target)  return mid;
                    pos_left = mid + 1;
                }
            }
    
            int left = 0,right = pos_left-1;
    
            while(left <= right)
            { 
                int mid = (left + right)/2;
                if(reader.get(mid) == target)    return mid;
                else if(reader.get(mid) < target)   left = mid + 1;
                else if(reader.get(mid) > target)   right = mid - 1;
            }
            return -1;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/13e76137adc34cbaa03d5e23362b7924.png