重点阐述二分查找、杨氏矩阵查找、查找出现次数超过一半的数以及字符串匹配算法。

1.有序数组的查找

给定一个排好序的数组，查找某个数是否在这个数组中， 请编程实现。

既然是有序数组，显而易见的想到使用二分查找。

以下是一份python参考实现：

def binarySearch(list_a, n, value):    left = 0    right = n-1    while left <= right:        middle = (left + right)/2        if list_a[middle] == value:            return middle        elif list_a[middle] > value:            right = middle-1        else:            left = middle+1    return -1

 

2.行列递增矩阵的查找

在一个m行n列的二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下的顺序排列。

现输入这样的一个二维数组和一个整数，请完成一个函数，判断数组中是否含有该函数。

def youngMatrix(matrix, value):    if matrix == []:        return False    m = len(matrix)    n = len(matrix[0])    x = 0    y = n-1    while x <= m-1 and y >= 0:        if matrix[x][y] == value:            return True        elif matrix[x][y] > value:            y -= 1        else:            x += 1    return False

 

3.出现次数超过一半的数

 

数组中有一个数出现的次数超过了数组长度的一半，找出这个数。

如果数组是无序的，可以使用堆栈每次删除两个不同的数，或是记录两个值的方法，或者直接使用快速排序使数列转化成有序。

如果数组本身是有序的，那么直接输出第n/2处的值即可。

def find_one_number(list_a, length):    candidate = list_a[0]    times = 1    for i in range(1, length):        if times == 0:            candidate = list_a[i]            times = 1        else:            if list_a[i] == candidate:                times += 1            else:                times -= 1    return candidate

4.字符串的查找

假设现在有这样一个问题，有一个文本串S和一个模式串P，要查找P在S中的位置该怎么做？

最经典的就是KMP算法。不过这里先介绍最容易理解的蛮力匹配方法。

def violence_match(str_s, str_p):    len_p = len(str_p)    len_s = len(str_s)    i = 0    j = 0    while i < len_s and j < len_p:        if str_s[i] == str_p[j]:            i += 1            j += 1        else:            i = i-j+1            j = 0    if j == len_p:        return i - j    else:        return -1