Binary Search 二分查找

Given a sorted array of n elements, write a function to search a given element x in array.

• Search算法里的入门算法，其实很多高级算法的思路都是以二分查找为基本思想引出的，特别是那些和logn相关的算法，比如说自平衡二叉树

经典二分查找

LintCode 457. Classical Binary Search

• 有序, 数组
• Why 链表不可以？Why 无序不可以？

class Solution:
    def findPosition(self, nums, target):
        if not nums: 
            return -1

        # 1 Two Pointers 指向可行解的范围
        start, end = 0, len(nums)-1

        while start <= end:
            # 2 Median Index 
            mid = start + (end - start) // 2

            # 3 Check Median Index Val
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                end = mid - 1   # Adjust end
            else:
                start = mid + 1 # Adjust start
        return -1

74. Search a 2D Matrix

• 一维Array和二维Matrix的转换
  • index => (x, y)
  • x = index / col
  • y = index % col

class Solution(object):
    def searchMatrix(self, matrix, target):
        if not matrix:
            return False
        m, n = len(matrix), len(matrix[0])
        start, end = 0, m*n-1
        while start <= end:
            mid = start + (end - start) / 2
            row, col = mid / n, mid % n
            if matrix[row][col] < target:
                start = mid + 1
            elif matrix[row][col] > target:
                end = mid - 1
            else:
                return True
        return False

九章算法二分查找模板

• while 循环 ?
  • while start + 1 < end, 留两个值做post processing
  • while start < end, 留一个值做post processing
  • while start < = end, 不留值
• 缩小查找范围 ?
  • start = mid 还是 start = mid + 1
  • end = mid 还是 end = mid + 1

def findPosition(self, A, target):
    if(len(A) == 0):
        return -1

    start = 0
    end = len(A) - 1

    while(start + 1 < end):
        mid = start + (end - start) / 2
        if(A[mid] == target):
            return mid
        if(A[mid] < target):
            start = mid
        else:
            end = mid

    #post processing
    if (A[start] == target):
        return start
    elif (A[end] == target):
        return end
    else:
        return -1

• Double Check 小技巧:
  • 当前这个mid对应的值是不是可能是要找的结果，mid + 1 还是 mid ?
  • start = mid 一定要用 while start + 1 < end !!!
  • 要找的结果是不是一定在数组当中！start < end 还是 start < = end