2

二分查找的简单理解 - 程序员翔仔

 1 year ago
source link: https://www.cnblogs.com/fatedeity/p/16441969.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

二分查找的搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找详细的执行步骤如下：

  1. 在有序表中，取中间记录作为比较对象；
  2. 若给定值与中间记录的关键字相等，则查找成功；
  3. 若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；
  4. 若给定值大于中间记录的关键字，则在中间记录的右半区继续查找；
  5. 不断重复步骤 1~4，直到查找成功，或所有查找区域无记录，查找失败为止。
二分查找

二分查找算法有哪些局限性？

二分查找算法需要按照下标随机访问。所以更适合数组结构，而不适合链表结构，数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。

二分查找针对的是有序数。二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中，针对动态变化的数据集合，二分查找将不再适用。

数据量太小不适合二分查找。在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多，只有数据量比较大的时候，二分查找的优势才会比较明显。

数据量太大也不适合二分查找。二分查找是作用在数组这种数据结构之上的，太大的数据用数组存储比较吃力，也就不能用二分查找了。

二分查找算法有哪些变形？

  • 查找第一个值等于给定值的元素
  • 查找最后一个值等于给定值的元素
  • 查找第一个大于等于给定值的元素
  • 查找最后一个小于等于给定值的元素
package cn.fatedeity.algorithm.search; public interface Search { int search(int[] numbers, int target);}

二分查找类

package cn.fatedeity.algorithm.search; /** * 二分查找类 */public class BinarySearch implements Search { private int search(int[] numbers, int target, int left, int right) { if (left > right) { return -1; } else if (left == right) { if (numbers[left] == target) { return left; } else { return -1; } } if (target < numbers[left] || target > numbers[right]) { return -1; } int mid = (left + right) >> 1; if (numbers[mid] > target) { return this.search(numbers, target, left, mid - 1); } else if (numbers[mid] < target) { return this.search(numbers, target, mid + 1, right); } else { return mid; } } @Override public int search(int[] numbers, int target) { return this.search(numbers, target, 0, numbers.length - 1); }}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK