算法基础：二分查找

2024-04-24 16:42:23 来源：力行文学网

二分查找是一种基本的搜索算法，它可以在有序数组中快速查找一个元素。在本文中，我们将详细介绍二分查找的原理和实现方法。

算法原理

二分查找算法的核心思想是不断将数组一分为二，直到找到目标元素为止。具体步骤如下：

将数组按照中间位置分成两个子数组
判断目标元素是在左子数组还是右子数组中
递归执行上述操作

需要注意的是，二分查找算法的前提是数组已经按照升序或者降序排列好了。

算法实现

下面是一个基本的二分查找算法实现：

 int binarySearch(int[] nums, int target) { int left = 0, 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; }

二分查找算法的时间复杂度为O(log n)，因为每次将数组大小减半。