简介
二分查找是一种在每次比较之后将查找空间一分为二的算法。二分查找的最大特点是：思路简单，实现很难。其原因是二分查找需要考虑循环的终止条件、mid的选取等细节，如果这些细节处理不当，稍有不慎就会出现问题。所以实际上二分查找仍是一个比较难的问题。
模板
模板1
基础模板。
C++
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
return -1;
}
Java
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
return -1;
}
Python
def binarySearch(nums,target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
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
模板2
高级模板。用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
C++
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size();
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
if(left != nums.size() && nums[left] == target) return left;
return -1;
}
Java
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
if(left != nums.length && nums[left] == target) return left;
return -1;
}
Python
def binarySearch(nums,target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
left,right = 0,len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid
if left != len(nums) and nums[left] == target:
return left
return -1
模板3
另一种独特形式。用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
C++
int binarySearch(vector<int>& nums, int target){
if (nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while (left + 1 < right){
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
Java
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
Python
def binarySearch(nums,target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
left,right = 0,len(nums) - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid
else:
right = mid
# Post-processing:
# End Condition: left + 1 == right
if nums[left] == target:return left
if nums[right] == target:return right
return -1
这 3 个模板的不同之处在于：
- 左、中、右索引的分配。
- 循环或递归终止条件。
- 后处理的必要性。
