# 公瑾总结

## Binary Search | 基础

``````left = 0, right = n -1
while (left <= right)
mid = (left + right) / 2
case
x[mid] < t:    left = mid + 1;
x[mid] = t:    p = mid; break;
x[mid] > t:    right = mid -1;
return -1;
``````

## Binary Search | 痛点

``````def binarySearch(arr, target):
l , r = 0, len(arr) - 1
while l <= r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return -1
``````

#### 痛点1: 溢出

`mid = (l+r)//2`

left = 1, right = Integer.MAX_VALUE

mid = l + (r-l)//2`

#### 痛点2: 边界错误

``````def binarySearch(arr, target):
l , r = 0, len(arr)
while l < r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return -1
``````

``````def binarySearch(arr, target):
'''
定义：在[l...r]的范围里寻找target, 因为这里定义是需要将r归入范围区间, inclusive，所以while循环的边界需要包含r
'''
l , r = 0, len(arr) - 1
while l <= r:

mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1   # 明确区间的要求，只要使用过的，一律绕过。
else:
r = mid - 1   # 明确区间的要求，只要使用过的，一律绕过。
return -1

``````

``````def binarySearch(arr, target):
'''
定义：在[l...r)的范围里寻找target, 因为这里定义是不需要将end归入范围区间
exclusive，所以while循环的边界小于End即可，因为length本身长度会比index大1
相对应的，每次target的value小于arr[mid]的时候，我们在重新定义新的end时候，
也选择exclusive的模式，r = mid即可
'''
l , r = 0, len(arr)
while l < r:
mid = l + (r-l)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid
return -1

``````

#### 痛点2.5 : 死循环

``````    l , r = 0, len(arr) - 1
while l <= r:
mid = l + (r-l)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid
else:
r = mid
return -1
``````

## Binary Search | 模板选择

@gengwuli 提出了模板一致性的观点，我也十分赞同。公瑾的策略是95%的情况下都用以下模板：

``````def binarySearch(arr, target):
l , r = 0, len(arr) - 1
while l <= r:
mid = (l+r)//2
if arr[mid] == target:
return mid
if target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return -1
``````

``````def binary_search(array, target):
start, end = 0, len(array) - 1
while start + 1 < end:
mid = (start + end) / 2
if array[mid] == target:
start = mid
elif array[mid] < target:
start = mid
else:
end = mid

if array[start] == target:
return start
if array[end] == target:
return end
return -1
``````

## Binary Search | 题型

1. 有明确Target
2. 没有明确Target
3. 没有明确Target (可越界类型）

### 第一类题：有明确Target的题型

#### Leetcode 374. Guess Number Higher or Lower

``````class Solution(object):
def guessNumber(self, n):
"""
:type n: int
:rtype: int
"""
l , r = 0 , n
while l <= r :
mid = l + (r-l)//2
toggle = guess(mid)
if toggle == 0:
return mid
if toggle == 1:
l = mid + 1
else:
r = mid - 1
``````

#### Leetcode 367. Valid Perfect Square

``````
class Solution:
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
l, r = 0, num
while l <= r:
mid = l + (r-l)//2
if mid ** 2 == num:
return True
if num > mid ** 2:
l = mid + 1
else:
r = mid - 1
return False
``````

#### 33. Search in Rotated Sorted Array

``````class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums: return -1
l , r = 0, len(nums) - 1

while l <= r:
mid = l + (r-l)//2
if target == nums[mid]:
return mid
if nums[mid] >= nums[l]:
if nums[l] <= target <= nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] <= target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1
``````

### 第二类题：没有明确Target的题型

• 比Target大的最小值
• 比Target小的最大值
• 满足要求的第一个值
• 不满足要求的最后一个值

Case 1:
`Array = [1,2,3,5,6], Target = 4`

`while l <= r:`

`L`对应的是：第一个比4大的坐标, 根据这道题的定义就是比Target大的最小值
`R`对应的是：最后一个比4小的坐标，根据这道题的定义就是比Target小的最大值

Case 2:
`Array = [1,2,3,5,6], Target = 7`

`l``r` 的位置和定义清楚了以后，我们来做做题。

#### 返回`l`的情况： 33. Search in Rotated Sorted Array

``````class Solution:
def searchInsert(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r-l)//2
if nums[mid] == target:
return mid
if target > nums[mid]:
l = mid + 1
else:
r = mid - 1
return l
``````

``````Input: [1,3,5,6], 2
Output: 1
``````

`l`的下标是1， 定义是第一个满足条件的最小值。
`r`的下标是0，定义是最后一个不满足条件的最大值。

#### 返回`r`的情况：458. Last Position of Target (Lintcode)

``````class Solution:
def lastPosition(self, nums, target):
if not nums:
return -1
l , r = 0 , len(nums) - 1
while l <= r:
mid = l + (r-l)//2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
if nums[r] == target:
return r
else:
return -1
``````

``````Input: [1, 2, 2, 4, 5, 5]
target = 2, return 2
``````

`l`的下标是3， 定义是第一个不满足条件的值
`r`的下标是2，定义是最后一个满足条件的值。

#### 楼上两题的合体：34. Search for a Range

``````class Solution:
def searchRange(self, nums, target):
l = self.findLeft(nums, target)
r = self.findRight(nums, target)
return [l, r] if l <= r else [-1, -1]

def findLeft(self, nums, target):
l, mid, r = 0, 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return l

def findRight(self, nums, target):
l, mid, r = 0, 0, len(nums)-1
while l <= r:
mid = l + (r-l)//2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
return r
``````

### 第三类题：没有明确Target的题型，可越界类型

#### 162. Find Peak Element

``````class Solution:
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l , mid , r = 0, 0, len(nums) - 1
while l + 1 < r:
mid = l + (r-l)//2
if nums[mid] < nums[mid + 1]:
l = mid
else:
r = mid
if nums[l] > nums[r]: return l
else: return r
``````

#### 153. Find Minimum in Rotated Sorted Array

``````class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, r = 0, len(nums) - 1
while l + 1 < r:
mid = l + (r - l) // 2
if nums[mid] > nums[r]:
l = mid
else:
r = mid
return min(nums[l], nums[r])
``````
2 Likes