有序数组,数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件。
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在nums 中因此返回 -1
python
class Solution(object): def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ l = 0 r = len(nums) # 左闭右开区间,不是左闭右闭区,算法截然不同 while(l < r): mid = (l + r) // 2 if(target > nums[mid]): l = mid + 1 elif(target < nums[mid]): r = mid else: return mid return -1
class Solution: def search(self, nums: List[int], target: int) -> int: l = 0 r = len(nums) - 1 # 左闭右闭 while(l <= r): mid = l + (r-l) // 2 # 避免区间越界 if(target > nums[mid]): l = mid + 1 elif(target < nums[mid]): r = mid - 1 else: return mid return -1
java
class Solution { public int search(int[] nums, int target) { int l = 0; int r = nums.length; // 左闭右开 while (l < r){ int mid = (l + r) / 2; if(target > nums[mid]){ l = mid + 1; }else if(target < nums[mid]){ r = mid; }else { return mid; } } return -1; } }
https://leetcode-cn.com/problems/binary-search
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF