题目地址：https://leetcode.com/problems/binary-search/description/
题目描述
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Note:
1、 Youmayassumethatallelementsinnumsareunique.；
2、 nwillbeintherange[1,10000].；
3、 Thevalueofeachelementinnumswillbeintherange[-9999,9999].；
题目大意
二分查找某个元素出现的位置。
解题方法
线性查找
这个题目名字叫做二分查找，但是给的测试用例使用10000个，那么完全可以线性查找，代码如下。
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
try:
return nums.index(target)
except:
return -1
1 2 3 4 5 6 7 8 9 10 11
二分查找
不懂为啥这么简单的题，没人做？
二分查找真是最基本的题目了吧，应该保证一遍就过的。就不多说了。
下面的做法是查找[left, right]闭区间。代码如下：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
如果是查找[left, right)左闭右开区间的话，代码如下：
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
N = len(nums)
left, right = 0, N
[0, N)
while left < right:
mid = left + (right - left) / 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid
else:
left = mid + 1
return -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发