什么是二分查找法

大家好，欢迎来到IT知识分享网。

二分查找法也称为折半查找法，是一种在有序数组中查找特定元素的算法。其原理是通过将数组中间的元素与目标元素进行比较，来确定目标元素可能存在的位置，并逐步缩小搜索范围。二分查找法的时间复杂度为O(log n)。

下面是java写的一个实例：

public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return -1; }

以上是一个简单的二分查找法实现，传入一个有序数组和目标元素，返回目标元素在数组中的位置。首先初始化左右指针为数组的首尾位置，然后在循环中求出中间位置，将中间位置的元素与目标元素进行比较，如果相等则返回该位置，如果中间位置的元素大于目标元素，则将右指针移动到中间位置的左侧，缩小搜索范围，否则将左指针移动到中间位置的右侧，同样缩小搜索范围。如果循环结束仍未找到目标元素，则返回-1表示未找到。