做菠菜网站判多久,食品建设网站前的市场分析,地图网站模板,深圳电器公司招聘信息Swift中的二分查找#xff1a;全面指南
简介
二分查找是计算机科学中的经典算法#xff0c;被广泛用于在已排序的数组中高效地搜索目标值。与线性查找逐个检查每个元素不同#xff0c;二分查找不断将搜索区间减半#xff0c;因此在处理大数据集时要快得多。
在这篇博客中…Swift中的二分查找全面指南
简介
二分查找是计算机科学中的经典算法被广泛用于在已排序的数组中高效地搜索目标值。与线性查找逐个检查每个元素不同二分查找不断将搜索区间减半因此在处理大数据集时要快得多。
在这篇博客中我们将探讨二分查找的基本原理它在Swift中的实现以及使其如此高效的底层概念。
理解二分查找
二分查找基于分治法的原理。以下是这个过程的逐步分解
初始设置从排序数组的开头低位和结尾高位各设置一个指针。找到中间值计算当前搜索区间的中间索引。比较将目标值与中间元素进行比较 如果目标值等于中间元素则搜索完成。如果目标值小于中间元素则将搜索区间缩小到左半部分。如果目标值大于中间元素则将搜索区间缩小到右半部分。 重复重复步骤2和3直到找到目标值或搜索区间为空。
Swift中的二分查找实现
以下是在Swift中实现二分查找的方法
func binarySearchT: Comparable(_ array: [T], target: T) - Int? {var low 0var high array.count - 1while low high {let mid (low high) / 2if array[mid] target {return mid} else if array[mid] target {low mid 1} else {high mid - 1}}return nil
}使用示例
让我们看看这个函数在一个示例中的工作方式
let sortedArray [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
if let index binarySearch(sortedArray, target: 7) {print(元素在索引 \(index) 处被找到)
} else {print(元素未找到)
}复杂度分析
二分查找的时间复杂度是O(log n)其中n是数组中的元素数量。这种效率来自于每一步都将搜索区间减半。迭代版本的空间复杂度是O(1)因为它只使用了常量级的额外空间。
边界情况和考虑
空数组如果数组为空函数应立即返回nil。不存在的元素如果目标值不在数组中函数应在耗尽搜索区间后返回nil。重复元素二分查找可以处理重复元素但它将返回其中一个出现的位置而不一定是第一个或最后一个。
结论
二分查找是一种高效的算法适用于在排序数组中进行搜索具有对数级时间复杂度。理解它的实现和行为对任何处理数据结构和算法的开发人员来说都是必不可少的。Swift的表达性语法使得在应用程序中实现和使用二分查找变得容易。 LeetCode (704. 二分查找)
题目描述
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
Swift Coding
class Solution {func search(_ nums: [Int], _ target: Int) - Int {}
}心得分析
核心是用前后两个指针控制搜索区间, 然后通过比较中间值与 target 值来不断缩小区间常见的错误思路是“试图仅通过一个指向中间值的指针来解决问题不断调整 centerPoint 找到 target 值”, 很快你会发现 centerPoint 的位置很难计算因为没有明确的搜索区间
