二分法查找

二分法查找

‌二分法查找是一种在有序数组中查找特定元素的搜索算法，其基本思想是将数组分成两半，通过比较目标值与中间元素的值来缩小搜索范围。如果目标值与中间元素相等，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。二分法查找的时间复杂度为O(logN)，空间复杂度为O(1)，因为它只需要常数级别的额外空间来存储中间变量。以下是二分法查找的C#实现示例代码：csharpCopy Codepublic static int BinarySearch(int[] nums, int low, int high, int target){ while (low <= high) { int middle = (low + high) / 2; if (target == nums[middle]) { return middle; } else if (target > nums[middle]) { low = middle + 1; } else { high = middle - 1; } } return -1; // 如果未找到目标值，返回-1}对于‌Java、C和‌Matlab等其他编程语言的实现，逻辑基本相同，只是语法和细节上略有不同。二分法查找的空间复杂度为O(1)，因为它不依赖于输入数据的大小而增加额外的存储空间。