算法-每天一道题(12)-二分查找

对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。
给定一个整数数组A及它的大小n,同时给定要查找的元素val,请返回它在数组中的位置(从0开始),若不存在该元素,返回-1。若该元素出现多次,请返回第一次出现的位置。

测试样例:

[1,3,5,7,9],5,3

返回:

1

Python

# -*- coding:utf-8 -*-

class BinarySearch:
    def getPos(self, A, n, val):
        # write code here
        n = self.findPos(A, 0, n-1, val)
        while True:
            if n == 0:
                return n
            else:
                if A[n-1] == A[n]:
                    n = n - 1
                else:
                    return n
    
    def findPos(self, A, start, end, value):
        if start == end:
            if (A[end] == value):
                return end
            else:
            	return -1
            
        if A[(end+start)/2] == value:
            return (end+start)/2
        elif A[(end+start)/2] < value:
            return self.findPos(A, (end+start)/2+1, end, value)
        else:
            return self.findPos(A, start, (end+start)/2-1, value)

'''
解题思路:

十分普通的二分查找,只是多了一个元素可能重复,加一个循环
'''

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部