二分查找模板
二分查找前提条件是个有序数组
设定左右指针
找出中间位置，并判断该位置值是否等于target
nums[mid] == target 则返回该位置下标
nums[mid] > target 则右侧指针移到中间
nums[mid] < target 则左侧指针移到中间
时间复杂度：O(logN)
int binarySearch(int[] nums, int target) {int left = 0, right = ...;while(...) {int mid = (right + left) / 2;if (nums[mid] == target) {...} else if (nums[mid] < target) {left = ...} else if (nums[mid] > target) {right = ...}}return ...;}
计算 mid 时需要技巧防止溢出，即 mid = left + (right - left) / 2。
go 语言实现
package main
import "fmt"
func binarySearch(nums []int,target int)int{
if len(nums)==0{
return -1
}
left :=0
right :=len(nums)-1
for left<=right{
mid := left+(right-left)>>1
if nums[mid]==target{
return mid
}else if nums[mid]>target{
right = mid-1
}else{
left = mid +1
}
}
return -1
}
func main() {
fmt.Println(binarySearch([]int{1,3,4,5,6,7},4))
fmt.Println(binarySearch([]int{1,3,4,5,6,7},8))
}
704. 二分查找
https://leetcode-cn.com/problems/binary-search/
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 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]之间。
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
go语言
func search(nums []int, target int) int {
if len(nums) == 0 {return -1}
count := len(nums)
l,r := 0, count - 1
for l<=r {
mid := l + ((r-l) >> 2)
if nums[mid] == target {
return mid
} else if nums[mid] > target{
r = mid - 1
} else {
l = mid + 1
}
}
return -1
}
c++
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
//两侧比较也可以省去
if (target == nums[0]) return 0;
if (target == nums[r]) return r;
while (l <= r) {
int mid = l + (r - l) / 2;
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
};
jdk 版本
//JDK里的代码
private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;//因为是闭区间，而toIndex是不在区间内的，所以需要-1
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
//这里的low和high分别在mid上进行加一和减一操作，也与左闭右闭保持了一致性
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
//这里针对 low==0 而无法判断是否找到的情况
return -(low + 1); // key not found.
}
python
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 确定查找的上下界
low, high = 0, len(nums) - 1
while low <= high: # 当low == high时还剩下最后一个值需要进行检验
mid = (low + high) // 2
if nums[mid] < target:
low = mid + 1 # +1是因为mid已经验证过不符合条件，新的区间又mid+1开始
elif nums[mid] > target:
high = mid - 1 # 这里+1同上面原因相同
else:
return mid
return -1 # 执行结束但是没有找到
278. 第一个错误的版本
https://leetcode-cn.com/problems/first-bad-version/
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
场景一：isBadVersion(mid) => false
1 2 3 4 5 6 7 8 9
G G G G G G B B B G = 正确版本，B = 错误版本
| | |
left mid right
场景一中，isBadVersion(mid) 返回 false，因此我们知道 mid 左侧（包括自身）的所有版本都是正确的。所以我们令 left=mid+1，把下一次的搜索空间变为 [mid+1,right]。
场景二：isBadVersion(mid) => true
1 2 3 4 5 6 7 8 9
G G G B B B B B B G = 正确版本，B = 错误版本
| | |
left mid right
场景二中，isBadVersion(mid) 返回 true，因此我们知道 mid 右侧（不包括自身）的所有版本的不可能是第一个错误的版本。所以我们令 right=mid，把下一次的搜索空间变为 [left,mid]。
在二分查找的每次操作中，我们都用left 和 right 表示搜索空间的左右边界，因此在初始化时，需要将 left 的值设置为 1，并将 right 的值设置为 n。当某一次操作后，left 和 right 的值相等，此时它们就表示了第一个错误版本的位置。
34. 在排序数组中查找元素的第一个和最后一个位置
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[start,end]区间二分查找，得到指定元素的索引midmid
如果mid=-1mid=−1，说明没有找到该元素，直接返回[-1,-1][−1,−1]
否则，该元素在数组中，开始寻找其左边界与右边界
初始化左边界prevprev，右边界postpost，值均为midmid
[start,prev-1][start,prev−1]区间二分查找，使用last\_prevlast_prev记忆上一次查找得到的索引
prev=-1prev=−1时，说明再也找不到了，此时last\_prevlast_prev即为左边界
[post+1,end][post+1,end]区间二分查找，使用last\_postlast_post记忆上一次查找得到的索引
post=-1post=−1时，说明再也找不到了，此时last\_postlast_post即为右边界
返回[last\_prev,last\_post][last_prev,last_post]
public int[] searchRange(int[] nums, int target) {
int start = 0, end = nums.length - 1, mid = 0;
if((mid = binarySearch(nums, start,end,target)) != -1){
int prev = mid, post = mid, last_prev = prev, last_post = post;
while(prev != -1){
last_prev = prev;
prev = binarySearch(nums, start, prev - 1, target);
}
while(post != -1){
last_post = post;
post = binarySearch(nums, post + 1, end, target);
}
return new int[]{last_prev, last_post};
}
else {
return new int[]{-1, -1};
}
}
private int binarySearch(int[] arr, int start, int end, int target){
while(start <= end){
int mid = (start + end) / 2;
if(arr[mid] == target){
return mid;
}
else if(arr[mid] > target){
end = mid - 1;
}
else {
start = mid + 1;
}
}
return -1;
}
35. 搜索插入位置
https://leetcode-cn.com/problems/search-insert-position/
package main
import "fmt"
func searchInsert(nums []int, target int) int {
left:=0
right:= len(nums)-1
for left<=right{
mid := (left+right) >>1
if nums[mid]==target {
return mid
} else if nums[mid] <target{
left=mid+1
}else {
right= mid-1
}
}
return left
}
func main() {
fmt.Println(searchInsert([]int{1,3,5,6},5))
fmt.Println(searchInsert([]int{1,3,5,6},7))
fmt.Println(searchInsert([]int{1},1))
}
230 二叉搜索中第K小的元素
参考
若有收获，就点个赞吧
0 人点赞
