查找

二分查找

在有序表中，取中间记录为比较对象，若给定值与中间记录的关键字相等，则查找成功，若给定值小于中间记录的关键字，则在中间记录的左半区继续查找，若给定值大于中间记录的关键字，则在右半区进行查找，不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

int Binary_Search(int *a,int n,int key)
{
    int low,high,mid;
    low = 1;   #定义最低下标记录为记录首位
    high = n;  #定义最高下标为记录末位
    while （low<=high）
    {
        mid = （low + high） / 2;
        if(key<a[mid])
            high = mid - 1;
        else if (key > a[mid])
            low = mid +1;
        else
            return mid;
     }
   return 0
    }
有序
O(logn)

面试题 10.05. 稀疏数组搜索

class Solution:
    def findString(self, words: List[str], s: str) -> int:
        left, right = 0, len(words) - 1
        while left <= right:
            mid = left + (right - left) // 2
            temp = mid  # 记录一下mid的位置，因为下面要移动mid来寻找非空串，如果查找失败需要用temp来恢复位置
            while words[mid] == '' and mid < right:  # 如果mid对应空串则向右寻找
                mid += 1
            if words[mid] == '':  
            # 该情况发生在mid走到了right-1的位置，如果right仍对应空，则说明temp右侧都是空，所以将右边界进行改变
                right = temp - 1
                continue
            if words[mid] == s:  # 该情况发生在mid在右移的过程中发现了非空串，则进行正常的二分查找
                return mid
            elif s < words[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return -1

350. 两个数组的交集 II

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        r = []
        left,right =0,0
        while left < len(nums1) and right<len(nums2):
            if nums1[left] <nums2[right]:
                left += 1
            elif nums1[left] == nums2[right]:
                r.append(nums1[left])
                left +=1
                right += 1
            else:
                right +=1
        return r

74. 搜索二维矩阵

注意到输入的 m x n 矩阵可以视为长度为 m x n的有序数组。

由于该 虚 数组的序号可以由下式方便地转化为原矩阵中的行和列 (我们当然不会真的创建一个新数组) ，该有序数组非常适合二分查找。

row = idx // n ， col = idx % n。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)   #行
        if m == 0:
            return False
        n = len(matrix[0])  #列
        left,right = 0,m*n-1
        while left <= right:
            pivot_idx = (left + right) // 2
            row = pivot_idx // n
            col = pivot_idx % n
            pivot_elenmnt = matrix[row][col]
            if pivot_elenmnt < target:
                left = pivot_idx + 1
            elif pivot_elenmnt > target:
                right = pivot_idx -1
            else:
                return True
        return False