二分查找(Binary Search)是一种在有序数组中查找特定元素的高效算法。它的基本思想是将目标值与数组中间的元素进行比较,如果目标值小于中间元素,则在数组的左半部分继续查找,否则在右半部分查找,不断缩小搜索范围,直到找到目标值或确定目标值不存在为止。
二分查找也叫折半查找,比如在一个有序的数组里面找到目标值,它是一种查询效率比较高的算法,时间复杂度O(logn)。比如在下面数组找到 6.首先在定位到两侧,也就是最大值和最小值。并找到中间和目标值比较。
中间值是 23,比目标值更大,就要缩小范围,中间值作为最大值,在中间值左边的区域再找到中间值和目标值比较。
以此类推,一直缩小范围,直到找到目标值,或者搜索完数据。
二分查找模板public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 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; // 目标值不存在
}
LeetCode 题解33.搜索旋转排序数组题目描述解题思路❝
left 和 right 记录最小值和最大值的下标,left (right - left) / 2 是查询中间下标,有的查询下标直接使用(left right)/2,这样可能会超出时间范围。通过 left = mid 1 或者 right = mid - 1 不断缩小范围。
❞
有序的数组在某个下标上进行旋转: