Binary Search

题目列表

问题描述

T(n) = T(n/2) + O(1) = O(log n)

面试中如果需要优化O(n)的时间复杂度，一般只能是O(logn)的二分法

常见问题

binary search可以有多种写法，如果每次都写的不一样，就会造成对于结束条件，指针变化的混乱，所以我们要找到一种固定的模板，通过修改模板来解决题目。这里我选择了九章算法提供的模板。

四点要素:

  1. start + 1 < end 这样就不用考虑两个指针的前后，最后结束时一定是相邻的
  2. start + (end - start) / 2 虽然对python来说不重要，但是对于Java等可以防止溢出
  3. A[mid] ==, <, > 这个会根据题目的不同来调整
  4. A[start] A[end] ? target
class Solution:
    # @param nums: The integer array
    # @param target: Target number to find
    # @return the first position of target in nums, position start from 0 
    def binarySearch(self, nums, target):
        if len(nums) == 0:
            return -1

        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start + end) / 2
            if nums[mid] < target:
                start = mid
            else:
                end = mid

        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1

最终状态都是要将start和end位置的值与target来比较，根据题意得到想要的结果

题型

Reference