leetcodeの二分探索の問題でめぐる式二分探索がうまくいかない理由

leetcodeの以下の問題で二分探索の勉強をしています。
シンプルな二分探索はできるのですが、以下のような応用的な問題でつまづきます。
leetcodeの問題

以下のようなキレイなコードがディスカッションにいくつも投稿されています。

Python
1def searchRange(self, nums, target):
2    def binarySearchLeft(A, x):
3        left, right = 0, len(A) - 1
4        while left <= right:
5            mid = (left + right) / 2
6            if x > A[mid]: left = mid + 1
7            else: right = mid - 1
8        return left
9
10    def binarySearchRight(A, x):
11        left, right = 0, len(A) - 1
12        while left <= right:
13            mid = (left + right) / 2
14            if x >= A[mid]: left = mid + 1
15            else: right = mid - 1
16        return right
17        
18    left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
19    return (left, right) if left <= right else [-1, -1]

しかしどれも”left”・"right"を、"mid"で更新していくときに、+1、-1が出てきます。このような実装も理解はできるようになりましたが、それでもコーナーケースの理解はややこしいので、「めぐる式二分探索」というのをwebで学んでから、普段はそれをベースにしていました。ですので、この問題も似たようなパターンで解けないか考えています。ですが、どうしてもうまく行きません。
めぐる式二分探索

私が最初に書いたコードは以下です。
あまりキレイではなく、読みにくくてすみません。

Python
1class Solution:
2    def searchRange(self, nums: List[int], target: int) -> List[int]:
3        # find end        
4        left = 0
5        right = len(nums) - 1
6        while right - left > 1:
7            mid = left + ((right - left) // 2)
8            if nums[mid] == target:
9                if mid == right or nums[mid + 1] > target:
10                    end = mid
11                    break
12
13            if self.isin_left_area(nums[mid], target):
14                right = mid
15            else:
16                left = mid
17        else:
18            end = -1      
19            
20        # find start   
21        left = 0
22        right = len(nums) - 1
23        while right - left > 1:
24            mid = left + ((right - left) // 2)
25            if nums[mid] == target:
26                if mid == left or nums[mid - 1] < target:
27                    start = mid
28                    break
29            
30            if self.isin_right_area(nums[mid], target):
31                left = mid
32            else:
33                right = mid
34        else:
35            start = -1
36
37        return [start, end]
38            
39    def isin_left_area(self, mid_val:int, target:int):
40        return mid_val > target
41   
42    def isin_right_area(self, mid_val:int, target:int):
43        return mid_val < target    
44

ケースとして、nums=[1], target=1やnums=[1, 1, 1], target=1などの場合がうまく行きません。開区間で考えようとすることで、リストnumsの先頭と末尾の判断ができないのが原因と思います。これらのケースは、「めぐる式二分探索」をベースにシンプルな実装をしようと思うと、例外として条件を作るしかないでしょうか。うまく実装できるような方法があれば教えていただきたいです。

行動規範の内容に同意します

回答1件

ベストアンサー

めぐる式が「半開区間」を前提としているのに、質問者さんのコードが「閉区間」で実装されているのがまずいのではないでしょうか。

質問者さんのコードだと、以下のように範囲をとっています。

python
1left = 0
2right = len(nums) - 1

leftもrightもnumsの添え字として有効な値となっているので、これは「閉区間」です。
「閉区間」でmidを+1,-1しない実装だと、leftとrightに挟まれる範囲が2未満にならない場合があります。
そうなると、ループを抜けた後でleft,right両方で条件判定して、正しい境界を見つけなければなりません。
こちらの方針で質問者さんのコードを修正すると、以下のようになります。

python
1class Solution:
2    def searchRange(self, nums: List[int], target: int) -> List[int]:
3        if not nums:
4            return [-1, -1]
5        # find end
6        left = 0
7        right = len(nums) - 1
8        while right - left > 1:
9            mid = left + ((right - left) // 2)
10            if self.isin_left_area(nums[mid], target):
11                right = mid
12            else:
13                left = mid
14        if self.isin_left_area(nums[left], target):
15            end = left - 1
16        elif self.isin_left_area(nums[right], target):
17            end = left
18        else:
19            end = right
20
21        # find start
22        left = 0
23        right = len(nums) - 1
24        while right - left > 1:
25            mid = left + ((right - left) // 2)
26            if self.isin_right_area(nums[mid], target):
27                left = mid
28            else:
29                right = mid
30        if self.isin_right_area(nums[right], target):
31            start = right + 1
32        elif self.isin_right_area(nums[left], target):
33            start = right
34        else:
35            start = left
36
37        return [start, end] if start <= end else [-1, -1]
38
39    def isin_left_area(self, mid_val:int, target:int):
40        return mid_val > target
41
42    def isin_right_area(self, mid_val:int, target:int):
43        return mid_val < target

めぐる式の「半開区間」でも、ループを抜けた後の条件判定が一度は必要になるので、めぐる式のベースである蟻本で採用している「開区間」を採用する方が、正直なところ実装は楽だと思います。
以下のソースで、left、rightともnumsの添え字の範囲外であることに注意してください。

python
1class Solution:
2    def searchRange(self, nums, target):
3        def binarySearchLeft(A, x):
4            left, right = -1, len(A)
5            while right - left > 1:
6                mid = (left + right) // 2
7                if A[mid] >= x: right = mid
8                else: left = mid
9            return right
10
11        def binarySearchRight(A, x):
12            left, right = -1, len(A)
13            while right - left > 1:
14                mid = (left + right) // 2
15                if A[mid] > x: right = mid
16                else: left = mid
17            return left
18
19        left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
20        return [left, right] if left <= right else [-1, -1]

二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜を読んで、やっとめぐる式の利点に気づいたので、今更ながら追記。

めぐる式で重要なのは、solveとそれが満たされる端ok、満たされない端ngさえ決まれば、あとは同じ書き方で済む点。半開区間か開区間かというのは重要ではなく、解きたい問題によって使い分ければいい。

今回の問題では、開始位置はnums[i] >= targetが満たされる最小のiにより、終了位置はnums[i] <= targetが満たされる最大のiにより求まるので、このように書ける。

python
1class Solution:
2    def searchRange(self, nums: List[int], target: int) -> List[int]:
3        def meguru(ok, ng, solve):
4            while abs(ok - ng) > 1:
5                mid = (ok + ng) // 2
6                if solve(mid): ok = mid
7                else: ng = mid
8            return ok
9        left = meguru(len(nums), -1, lambda i: nums[i] >= target)
10        right = meguru(-1, len(nums), lambda i: nums[i] <= target)
11        return [left, right] if left <= right else [-1, -1]

投稿2021/10/17 03:37

編集2021/10/21 13:07

actorbug

総合スコア2235

fu_3823

2021/10/17 08:29

何度も丁寧な回答ありがとうございます。理解不足の箇所を指摘いただけ、大変勉強になりました。

fu_3823

2021/10/22 02:17

ありがとうございます。わかったつもりでいた二分探索ですが、「開区間、半開区間、閉区間」について、それぞれの場合のアルゴリズムの解釈の仕方と、めぐる式の半開区間を選択する理由がうまくつながリませんでした。しかし、追記していただいた内容を読んで、「求めたい範囲の条件（右端、左端を含むかどうか）」と、「区間の決め方（開・半開・閉区間）」の関係にやっと気づくことができました。

行動規範の内容に同意します