LeetCode 704. 二分查找

题目

给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。

算法要求

线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

方法

• 将数据变成有序数据
• 确定此区间的最小下标low、最大下标high和中间下标mid
• 若low ≤ high，则一直循环：
  判断mid所对应的值是否等于想要查找的值，若是，则返回mid，结束循环
  判断mid所对应的值是否小于想要查找的值，若是，则low = mid + 1
  判断mid所对应的值是否大于想要查找的值，若是，则high = mid - 1
• 若以上均不成立，则此数值不在数据中，返回-1

class Solution(object):
    def search(self, nums, target):
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if target == nums[mid]:
                return mid 
            elif target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        return -1

相关知识

• 二分查找：
  要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列
  • 将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功
  • 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表
  • 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功

参考

代码相关：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html