# Dichotomy search

## thinking

By maintaining the three indexes in the left, middle and right, we constantly lose half of the impossible search space, and continue to search in the other half until success

The basic dichotomous template is as follows:

``````    def search(self, nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] <target:
left = mid+1
else:
right = mid-1
return -1
``````

Using the basic dichotomous template, we can find the square root and guess the number

## Search rotation sort array

The topic requires time complexity O(logn), so the binary search method is selected

Because the sorting array rotates, only one side can keep order after dividing two sides

If the left side is in order and the target value is in the left side range, it is normal dichotomy, otherwise, it is taken as the right side
If the right side is in order and the target value is in the right side range, the normal score is two points, otherwise, the left side is taken

``````def search(self, nums, target):
left = 0
right = len(nums)-1
while left <= right:
mid = (left + right) // 2
n = nums[mid]
print(left,right,n)
if n == target:
return mid
if n > nums[left]:
if n > target and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
elif n < nums[right]:
if n < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
left += 1
return -1
``````

## First wrong version

The difference from the previous one is to find the dividing point between error and non error, so there is a side that can't skip mid and ensure that a left is the last correct version and a right is the first wrong version

``````def firstBadVersion(self, n):
left = 0
right = n
while left < right:
mid = (left+right)//2

right = mid
else:
left = mid + 1
return left
``````

## Looking for peaks

You need to directly access the right element and select the left side to ensure that mid = right

``````class Solution:
def findPeakElement(self, nums):
if len(nums) == 0:
return 0
left = 0
right = len(nums)-1
while left<right:
mid = (left+right)//2
if nums[mid]>nums[mid+1]:
right = mid
else:
left = mid + 1
return left
``````

## Find the minimum value in the rotation sort array

The array value must be greater than the previous item. If the mid is less than the last item, the right ordered minimum value is on the left
If mid is greater than last, the minimum value is on the right

It can be further modified. Left and right are in order and return to left directly

``````      def findMin(self, nums):
left = 0
right = len(nums)-1
while left<right:

if nums[left]<nums[right]:
return nums[left]

mid = (left+right)//2
n = nums[mid]
if n<nums[mid-1]:
return n
elif n>=nums[left] :
left = mid + 1
else:
right = mid

return nums[left]
``````

Keywords: less

Added by poisedforflight on Sun, 22 Dec 2019 21:03:03 +0200