题目704. 二分查找 - 力扣LeetCode给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果target存在返回下标否则返回-1。你必须编写一个具有O(log n)时间复杂度的算法。示例 1:输入:nums [-1,0,3,5,9,12],target 9输出:4解释:9 出现在nums中并且下标为 4示例 2:输入:nums [-1,0,3,5,9,12],target 2输出:-1解释:2 不存在nums中因此返回 -1提示你可以假设nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。题解梦开始的地方解题思路方法二分查找时间复杂度: O(logN)过程设定整个数组或者扩大一点说整个区间的左右边界可命名为left和right设立中间值mid(left right)/2让这个程序不断循环即使用while条件设定为左边界left 右边界right这是区间成立的必要条件。当循环条件不成立时即意味着整个数组没有符合target的值返回-1程序结束每进入一个循环都要进行以下判断nums[mid] target直接找出target返回数组下标midnums[mid] target缩小范围此时target在left和mid之间mid作为新的右边界rightnums[mid] target缩小范围此时target在mid和right之间mid作为新的左边界left易错点 边界问题while循环的条件left 小于 right要不要等于这个其实可以看成一个区间即【left,right】【 符号表示闭区间即区间包含left和right两个数当你看作左闭区加右闭区间的时候那么就是leftright因为【11】是成立的当你看成【leftright时那么不能加上等号因为【11 不能即包含又不包含值得注意的是当你选择了一种区间方式那么整道题目都必须按照这个区间来while循环里面的if判断完后的左右边界要不要加1或者减1当你选择【leftright】时由于左右边界被包含同时被if进行了判断所以替换边界时替换左边界left要加上1替换右边界right要减去1都取靠中间的相邻数字。注意当你选择【leftright】时我们的右边界为数组大小-1因为数组下标是从0开始的类似right nums.size -1当你选择【leftright时由于right不被包含所以取数组大小类似right nums.size图解![[二分法.excalidraw]]代码实现以下代码都按照【leftright】来写的伪代码left 0 right nums.size - 1 while(){ if nums[mid] target return mid if nums[mid] target right mid - 1 if nums[mid] target left mid 1 } return -1Java实现class Solution { public int search(int[] nums, int target) { int left 0, right; right nums.length-1; while(left right){ int mid; mid (left right)/2; if (nums[mid] target) { left mid 1; } else if (nums[mid] target) { right mid -1; } else if (nums[mid] target) { return mid; } } return -1; } }C语言实现int search(int* nums, int numsSize, int target) { int left 0; int right numsSize - 1; while (left right) { // 写成 left (right - left) / 2而不是 (left right) / 2 // 这样在 left 和 right 都很大时可以避免相加溢出是更稳妥的写法 int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else if (nums[mid] target) { right mid - 1; } else { return mid; } } return -1; }Python实现from typing import List class Solution: def search(self, nums: List[int], target: int) - int: left, right 0, len(nums) - 1 while left right: # 注意 Python 的 / 是浮点除法取中间下标要用整除 // mid (left right) // 2 if nums[mid] target: left mid 1 elif nums[mid] target: right mid - 1 else: return mid return -1参考代码随想录代码随想录·文字版 704.二分查找力扣官方题解题目页里的题解区OI Wiki·二分Hello 算法开源算法教程同一份代码有 Java / C / Python 三个版本
