丹阳网站建设报价文件外链网站

任务背景

---

问题来自力扣题目704：Binary Search，大意如下：

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

翻译下，需求是：对有序数组进行查找指定数字，若有返回索引，若无返回-1.

思路分析

---

重温下二分写法，思路很简单，发现值大的下移上界，发现值小的上移下界，直到上下界重合。

要注意的是无target时，mid的偏移问题。

代码实现

---

class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""# range: [low, high)low = 0high = len(nums)while (low < high):mid = low + (high - low) // 2if nums[mid] < target:low = mid + 1elif nums[mid] > target:high = midelse:return mid# not foundreturn -1# test
nums = [-1, 0, 3, 5, 9, 12]
target = 9# nums = [-1,0,3,5,9,12]
# target = 2sol = Solution()
res = sol.search(nums, target)
print(res)

测试套件

---

# 导入单元测试
import unittest# 编写测试套
class TestSol(unittest.TestCase):# 不在数组中def test_special1(self):nums = [-1, 0, 3, 5, 9, 12]target = 2ret = -1sol = Solution()self.assertEqual(sol.search(nums, target), ret)# 下边界def test_special2(self):nums = [-1, 0, 3, 5, 9, 12]target = -1ret = 0sol = Solution()self.assertEqual(sol.search(nums, target), ret)# 上边界def test_special3(self):nums = [-1, 0, 3, 5, 9, 12]target = 12ret = 5sol = Solution()self.assertEqual(sol.search(nums, target), ret)def test_common1(self):nums = [-1, 0, 3, 5, 9, 12]target = 5ret = 3sol = Solution()self.assertEqual(sol.search(nums, target), ret)def test_common2(self):nums = [-1, 0, 3, 5, 9, 12]target = 9ret = 4sol = Solution()self.assertEqual(sol.search(nums, target), ret)# 含测试套版本主调
if __name__ == '__main__':print('start!')unittest.main() # 启动单元测试print('done!')

本文小结

---

二分核心：索引偏移存乎一心。

可进一步思考若有重复值时，如何找到最小重复索引或最大重复索引。