算法之二分查找
二分查找思想
二分查找思想
二分查找又叫折半查找，是一种有序查找算法，必须先排序后查找！ 将首尾两位各自定义一个指针，计算出一个折半位置mid
将给定值target与折半位置mid比较有以下三种情况:
给定数组 nums[5,6,7,9,10,14,15,56]，给定target[15]
首指针为0（下标），尾指针nums.length-1，折半位置 (left + right) >>> 1
1. target > mid
当给定值target大于折半位置mid，说明你要找的值肯定在mid右半部分。所以我们把首指针指到(mid+1)位置缩小查找范围。
2. target < mid
当给定值target小于于折半位置mid，说明你要找的值肯定在mid左半部分。所以我们把尾指针指到(mid-1)位置缩小范围。
3. target = mid
正好等于，直接返回
动态二分查找图
具体代码实现
- Java
- Python
public static int twoSelect(int[] nums, int target) {
// 首指针
int left = 0;
// 尾指针
int right = nums.length - 1;
// 边界 首指针 <= 尾指针
while (left <= right) {
int mid = (left + right) >>> 1;
if (target == nums[mid]) {
return mid;
}
if (target > nums[mid]) {
left = mid + 1;
}
if (target < nums[mid]) {
right = mid - 1;
}
}
return -1;
}
总结
二分查找
二分查找的时间复杂度是:O(logn) n就是数组的长度，空间复杂度O(1)，在大量有序数据中查找特定的值是一个不错的选择。