方針１で解いた場合、Time Limit Exceededで失敗しました。
二分探索を用いた方針2で解いこうとしましたが、失敗しました。おそらく二分探索の実装が間違っています。
線形探索を用いた方針3で解き、成功しました。
追記に、二分探索で成功したということを書いています。

問題

こちらから挑戦することができます。
https://leetcode.com/problems/first-missing-positive/

ソートされていない整数配列numsが与えられています。欠けている最小の正の整数を返してください。

O(n)時間で実行され、一定の空間を使用するアルゴリズムを実装する必要があります。

（例と制約についてはリンク先のページにあるので省略します。）

方針1

numsの最大の数を探す。
最大の数が正の整数でないなら、1を返す。
最大の数が正の数ならば以下を行う。
1から最大の数+1までの数を要素とした集合を作る。…①
numsのうち正である数だけを採った集合を作る。…②
②のうち①に含まれないもののうち最小の数を採り、それを返す。

提出したコード

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        #ソートしても問題ない場合、何も考えずにソートします。
        nums.sort()

        # numsの最大の数
        max_nums = max(nums)

        if max_nums <= 0: #0は正の整数に含まれないので、0以下を条件にします。
            return 1
        else: # max_numsが正の整数の場合
            # candidates: 返される数の候補たち。1からmax_nums + 1まで。
            candidates = {i for i in range(1, max_nums + 2)}
            # pos_nums: numsのうち正である数
            pos_nums = {x for x in nums if x >= 1}

            # 候補の中の最小の数を返す。
            return min(candidates - pos_nums)

結果：Time Limit Exceeded

反省1

たとえpos_numsの要素が1個だけでも、それが100000000とかであった場合、candidatesに対して100000000個の要素を作らなければならないです。
それが原因してTime Limit Exceededを起こしたものと思われます。

方針2

numsをソートする。
numsの中の正の数だけを採った配列pos_numsを用意する。
pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を調べる。それぞれ、配列の最も右の数、最も左の数である。
min_pos_numが2以上ならば、1を返す。
min_pos_numが1ならば、以下を考える。
仮に、pos_numsが、正の数が欠けていない配列ならば、sum(pos_nums) == (1 + len(pos_nums)) * len(pos_nums) / 2が成り立つ。その場合には、max_pos_num + 1を返す。
仮に、pos_numsが、正の数が欠けていない配列ならば、その位置と内容の間には pos_nums[i] == i + 1 の関係が成り立つ。
内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、その場所の直前の左の数に1を加えたものを、答えとして返す。
探索には二分探索を用いる。

提出したコード2

import math

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # ソートしても問題ない場合、何も考えずにソートします。
        # もともとの配列に数字が重複している場合があるので、それをsetを使って削除します。
        nums = sorted(list(set(nums)))

        # numsの最大の数
        max_num = max(nums)

        if max_num <= 0: #0は正の整数に含まれないので、0以下を条件にします。
            return 1

        # pos_nums: numsのうち正である数
        pos_nums = [x for x in nums if x >= 1]

        # pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を取得する。
        # それぞれ、配列の最も右の数、最も左の数である。
        max_pos_num = pos_nums[-1]
        min_pos_num = pos_nums[0]

        # min_pos_numが2以上ならば、1を返す。
        if min_pos_num >= 2:
            return 1

        # 以下は、min_pos_numが1の場合。

        # 仮に、pos_numsが、正の数が欠けていない配列ならば、
        # それは初項 1，公差 1，項数 max_pos_numの等差数列である。等差数列の和の公式より、
        # sum(pos_nums) ==  (1 + len(pos_nums)) * len(pos_nums) / 2
        # が成り立つ。
        # その場合には、len(pos_nums) + 1を返す。

        if sum(pos_nums) ==  (1 + len(pos_nums)) * len(pos_nums) / 2:
            return len(pos_nums) + 1

        # 以下は、pos_numsが等差数列ではない場合。

        # 仮に、pos_numsが、正の数がかけていない配列ならば、その位置と内容の間には
        # pos_nums[i] == i + 1
        # の関係が成り立つ。
        # 内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、
        # その場所の直前の左の数に1を加えたものを、答えとして返す。
        # この探索には、今回は線形探索を用いる。

        #l: 二分探索の左側の端
        #r: 二分探索の右側の端
        #c: 二分探索の中央を示す。
        l = 0
        r = len(pos_nums) - 1
        c = math.ceil((l + r) / 2)

        while True:
            # lとrが等しい時には、探索を終了する。
            if l == r:
                #l, r, cが示している場所は、等差数列を乱しているラインの右でもありうるし、左でもありうる。
                #pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの左側である。
                #l == 0 の場合も、そのラインの左側である。
                if l == 0 or pos_nums[c] - pos_nums[c - 1] == 1:
                    return pos_nums[c] + 1
                elif r == len(pos_nums) - 1 or  pos_nums[c] - pos_nums[c - 1] != 1:
                #pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの右側である。
                    return pos_nums[c - 1] + 1

                return res

            # pos_nums[c] == c + 1 が成り立つならば、lを現在のcより1つ右にずらす。
            # そのうえでcを更新する。
            if pos_nums[c] == c + 1:
                l = c + 1
                c = math.floor((l + r) / 2)
                continue
            # pos_nums[c] == c + 1 が成り立たないならば、rを現在のcより1つ左にずらす。
            # そのうえでcを更新する。
            else:
                r = c - 1
                c = math.floor((l + r) / 2)
                continue 

        # 探索してもズレが見つからなかった場合には、-1を返す。
        return -1

結果：Time Limit Exceeded

反省2

二分探索の実装が間違っていると思われます。

方針3

背伸びせずに、線形探索で探索を行います。

提出したコード3

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # ソートしても問題ない場合、何も考えずにソートします。
        # もともとの配列に数字が重複している場合があるので、それをsetを使って削除します。
        nums = sorted(list(set(nums)))

        # numsの最大の数
        max_num = max(nums)

        if max_num <= 0: #0は正の整数に含まれないので、0以下を条件にします。
            return 1

        # pos_nums: numsのうち正である数
        pos_nums = [x for x in nums if x >= 1]

        # pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を取得する。
        # それぞれ、配列の最も右の数、最も左の数である。
        max_pos_num = pos_nums[-1]
        min_pos_num = pos_nums[0]

        # min_pos_numが2以上ならば、1を返す。
        if min_pos_num >= 2:
            return 1

        # 以下は、min_pos_numが1の場合。

        # 仮に、pos_numsが、正の数が欠けていない配列ならば、
        # それは初項 1，公差 1，項数 max_pos_numの等差数列である。等差数列の和の公式より、
        # sum(pos_nums) ==  (1 +len(pos_nums)) * len(pos_nums) / 2
        # が成り立つ。
        # その場合には、max_pos_num + 1を返す。

        if sum(pos_nums) ==  (1 + len(pos_nums)) * len(pos_nums) / 2:
            return len(pos_nums) + 1
        
        # 以下は、pos_numsが等差数列ではない場合。

        # 仮に、pos_numsが、正の数がかけていない配列ならば、その位置と内容の間には
        # pos_nums[i] == i + 1
        # の関係が成り立つ。
        # 内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、
        # その場所の直前の左の数に1を加えたものを、答えとして返す。
        # この探索には、今回は線形探索を用いる。

        for i, num in enumerate(pos_nums, start = 1):
            if i != num:
                # その場所の直前の左の数に1を加えたもの : i - 1 + 1 == i
                return i

        # 探索してもズレが見つからなかった場合には、max_pos_num + 1を返す。
        return max_pos_num + 1

結果：Success

反省3

解けて気持ちいいので反省は特にないです！！！！！！！

追記：二分探索に成功しました。

二分探索に失敗していた原因は、lとrの差が1の時に、lがrより大きくなったり、rがlより小さくなったりすることです。

おかしくなる条件がわかっているのでif文を用いて厳密に書いてもいいものの、ネストが深くなって将来の私にとって読めなくなるので、maxとminを使ってどうにかします。

import math

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # ソートしても問題ない場合、何も考えずにソートします。
        # もともとの配列に数字が重複している場合があるので、それをsetを使って削除します。
        nums = sorted(list(set(nums)))

        # numsの最大の数
        max_num = max(nums)

        if max_num <= 0: #0は正の整数に含まれないので、0以下を条件にします。
            return 1

        # pos_nums: numsのうち正である数
        pos_nums = [x for x in nums if x >= 1]

        # pos_numsの最大の数(max_pos_num)、最小の数（min_pos_num）を取得する。
        # それぞれ、配列の最も右の数、最も左の数である。
        max_pos_num = pos_nums[-1]
        min_pos_num = pos_nums[0]

        # min_pos_numが2以上ならば、1を返す。
        if min_pos_num >= 2:
            return 1

        # 以下は、min_pos_numが1の場合。

        # 仮に、pos_numsが、正の数が欠けていない配列ならば、
        # それは初項 1，公差 1，項数 max_pos_numの等差数列である。等差数列の和の公式より、
        # sum(pos_nums) ==  (1 + len(pos_nums)) * len(pos_nums) / 2
        # が成り立つ。
        # その場合には、len(pos_nums) + 1を返す。

        if sum(pos_nums) ==  (1 + len(pos_nums)) * len(pos_nums) / 2:
            return len(pos_nums) + 1

        # 以下は、pos_numsが等差数列ではない場合。

        # 仮に、pos_numsが、正の数がかけていない配列ならば、その位置と内容の間には
        # pos_nums[i] == i + 1
        # の関係が成り立つ。
        # 内容 = 位置 + 1の関係が成り立たない最も左の場所を探し、
        # その場所の直前の左の数に1を加えたものを、答えとして返す。
        # この探索には、今回は線形探索を用いる。

        #l: 二分探索の左側の端
        #r: 二分探索の右側の端
        #c: 二分探索の中央を示す。
        l = 0
        r = len(pos_nums) - 1
        c = math.ceil((l + r) / 2)

        while True:
            # lとrが等しい時には、探索を終了する。
            if l == r:
                #l, r, cが示している場所は、等差数列を乱しているラインの右でもありうるし、左でもありうる。
                #pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの左側である。
                #l == 0 の場合も、そのラインの左側である。
                if l == 0 or pos_nums[c] - pos_nums[c - 1] == 1:
                    return pos_nums[c] + 1
                elif r == len(pos_nums) - 1 or  pos_nums[c] - pos_nums[c - 1] != 1:
                #pos_nums[c] - pos_nums[c - 1] == 1 ならば、そのラインの右側である。
                    return pos_nums[c - 1] + 1

                return res

            # pos_nums[c] == c + 1 が成り立つならば、lを現在のcより1つ右にずらす。
            # そのうえでcを更新する。
            if pos_nums[c] == c + 1:
                l = min([r, c + 1])
                c = math.floor((l + r) / 2)
                continue
            # pos_nums[c] == c + 1 が成り立たないならば、rを現在のcより1つ左にずらす。
            # そのうえでcを更新する。
            else:
                r = max([l, c - 1])
                c = math.floor((l + r) / 2)
                continue 

        # 探索してもズレが見つからなかった場合には、-1を返す。
        return -1

結果：

イイ感じですね！