前端大厂最新面试题-BinarySearch.docx

二分查找算法 二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。要应用二分查找法，数组应具有以下特性： * 存储在数组中 * 有序排序 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到这种搜索算法每一次比较都使搜索范围缩小一半。 相比普通的顺序查找，除了数据量很少的情况下，二分查找会比顺序查找更快。二分查找的时间复杂度为 O(logn)，而顺序查找的时间复杂度为 O(n)。 在实现二分查找时，需要考虑数组中是否存在重复项。如果数组中不存在重复项，可以使用以下代码实现： ```javascript function BinarySearch(arr, target) { if (arr.length <= 1) return -1 let lowIndex = 0 let highIndex = arr.length - 1 while (lowIndex <= highIndex) { const midIndex = Math.floor((lowIndex + highIndex) / 2) if (target < arr[midIndex]) { highIndex = midIndex - 1 } else if (target > arr[midIndex]) { lowIndex = midIndex + 1 } else { return midIndex } } return -1 } ``` 如果数组中存在重复项，而我们需要找出第一个制定的值，可以使用以下代码实现： ```javascript function BinarySearchFirst(arr, target) { if (arr.length <= 1) return -1 let lowIndex = 0 let highIndex = arr.length - 1 while (lowIndex <= highIndex) { const midIndex = Math.floor((lowIndex + highIndex) / 2) if (target < arr[midIndex]) { highIndex = midIndex - 1 } else if (target > arr[midIndex]) { lowIndex = midIndex + 1 } else { if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex highIndex = midIndex - 1 } } return -1 } ``` 此外，还有一种特殊的数组可以应用二分查找，即轮转后的有序数组。这种数组的特性是存在一个分界点，用来分界两个有序数组。代码实现如下： ```javascript function search(nums, target) { if (nums == null || !nums.length) { return -1; } let begin = 0, end = nums.length - 1; while (begin <= end) { let mid = begin + Math.floor((end - begin) / 2); if (nums[mid] === target) { return mid; } else if (nums[begin] <= nums[mid]) { if (nums[begin] <= target && target < nums[mid]) { end = mid - 1; } else { begin = mid + 1; } } else { if (nums[mid] < target && target <= nums[end]) { begin = mid + 1; } else { end = mid - 1; } } } return -1; } ``` 二分查找算法是一种高效的搜索算法，应用于有序数组中查找特定元素。但是，需要根据实际情况选择合适的实现方式，并考虑数组中是否存在重复项。