题目描述

• 一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0~n-1 之内
• 在范围 0~n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字

题目解读

• 剑指Offer 266

代码

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int GetMissingNumberCore(vector<int>& data, int left, int right){
        if(left <= right){
            int index = (left + right) >> 1;
            int mid = data[index];

            // 如果中间元素的值和下标相等，那么下一轮只需要查找右半边
            if(mid == index){
                left = index+1;
            }
            else{
                // 如果中间元素的值和下标不想等，并且它前面一个元素和它的下标相等，
                // 这意味着这个中间的数字正好是第一个值和下标不想等的元素
                if((index == 0) || (index-1 == data[index-1])){ // 0 缺失，坐标0前面没有数值，所以防止越界单独拿出来考虑
                    return index;
                }
                else{ 
                    // 如果中间元素的值和下标不想等，并且它前面一个元素和它的下标
                    // 不相等，者意味着下一轮查找我们只需要在左半边查找即可
                    right = index-1;
                }
            }
            return GetMissingNumberCore(data, left, right);
        }
    }

    int GetMissingNumber(vector<int> data) {
        int length = data.size();
        if(length == 0){
            return 0;
        }

        return GetMissingNumberCore(data, 0, length-1);
    }
};


int main(){
    Solution ss;
    int len = 8;
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8};

    vector<int> data;
    for(int i=0; i < len; i++){
        data.push_back(a[i]);
    }
    cout<<ss.GetMissingNumber(data);
}

总结展望

• 二分查找功能真是强大啊