对于一个有序数组,我们通常采用二分查找的方式来定位某一元素,请编写二分查找的算法,在数组中查找指定元素。
给定一个整数数组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) ''' 解题思路: 十分普通的二分查找,只是多了一个元素可能重复,加一个循环 '''