网站访客记录 是后台做吗,网络学校,室内艺术设计,Wordpress支持分布发布吗二分查找#xff08;Binary Search#xff09;算法#xff0c;也叫折半查找算法#xff0c;是一种针对有序数据集合的查找算法。
1-二分查找的思想 我们生活中猜数字的游戏#xff0c;告诉你一个数据范围#xff0c;比如0-100#xff0c;然后你说出一个数字#xff0c…二分查找Binary Search算法也叫折半查找算法是一种针对有序数据集合的查找算法。
1-二分查找的思想 我们生活中猜数字的游戏告诉你一个数据范围比如0-100然后你说出一个数字我告诉你的目标数字比你的大还是小你继续猜根据二分查找的思想你只要几次就可以猜中。比如目标值68。 每次猜一个数字通过告知结果后排除掉一半的数字这种思想就是二分查找。 二分查找针对的是一个有序的数据集合查找思想有点类似分治思想。每次都通过跟区间的中间元素对比将待查找的区间缩小为之前的一半直到找到要查找的元素或者区间被缩小为0。 折半的思想从而使得二分查找的时间复杂度是O(logn)。这是一种极其高效的时间复杂度因为logn是一个非常“恐怖”的数量级即便n非常非常大对应的logn也很小。比如n等于2的32次方大约是42亿。也就是说如果我们在42亿个数据中用二分查找一个数据最多需要比较32次。
2-二分查找实现 假设数组中不存在重复的元素数组中的元素有序并且从小到大排序好查找数组中是否存在某个元素存在就返回元素在数组中的下标不存在就返回-1。 /*** 查询数组中等于 target 的 索引* 数组中没有重复的元素** param array 待查找的数组* param target 目标值* return 数组下标索引没有查询到返回-1*/
private static int binarySearch01(int[] array, int target) {int low 0;int high array.length - 1;while (low high) {int mid low ((high - low) 1);if (array[mid] target) {return mid;}if (array[mid] target) {high mid - 1;}if (array[mid] target) {low mid 1;}}return -1;}
3-二分查找的特点
(1)二分查找依赖的是顺序表结构简单点说就是数组。 (2)二分查找针对的是有序数据。 (3)数据量太小不适合二分查找。但是如果数据之间的比较操作非常耗时不管数据量大小我都推荐使用二分查找。比如数组中存储的都是长度超过300的字符串如此长的两个字符串之间比对大小就会非常耗时。我们需要尽可能地减少比较次数而比较次数的减少会大大提高性能这个时候二分查找就比顺序遍历更有优势。 (4)数据量太大也不适合二分查找。二分查找的底层需要依赖数组这种数据结构而数组为了支持随机访问的特性要求内存空间连续对内存的要求比较苛刻。
4-二分查找的变形问题
4.1-查找第一个值等于给定值的元素 上面的二分查找算法中要求数组中存在不重复的数字现在我们取消这个限制查找数组中第一个值等于给定值的元素。 /*** 查询数组中第一个等于target的数字返回数组的索引** param array 目前数组* param target 目标值* return 数组下标索引没有查询到返回-1*/private static int binarySearch02(int[] array, int target) {int low 0;int high array.length - 1;while (low high) {int mid low ((high - low) 1);if (array[mid] target) {if ((mid 0) || array[mid - 1] ! target) {return mid;} else {high mid - 1;}}if (array[mid] target) {high mid - 1;}if (array[mid] target) {low mid 1;}}return -1;} 如果mid等于0那这个元素已经是数组的第一个元素那它肯定是我们要找的如果mid不等于0但a[mid]的前一个元素a[mid-1]不等于value那也说明a[mid]就是我们要找的第一个值等于给定值的元素。
4.2-查找最后一个值等于给定值的元素 要求数组中存在不重复的数字现在我们取消这个限制查找数组中最后一个值等于给定值的元素。 /*** 查询数组中最后一个等于target的数字返回数组的索引** param array 目前数组* param target 目标值* return 数组下标索引没有查询到返回-1*/private static int binarySearch03(int[] array, int target) {int low 0;int maxIndex array.length - 1;int high array.length - 1;while (low high) {int mid low ((high - low) 1);if (array[mid] target) {if ((mid maxIndex) || array[mid 1] ! target) {return mid;} else {low mid 1;}}if (array[mid] target) {high mid - 1;}if (array[mid] target) {low mid 1;}}return -1;} 如果a[mid]这个元素已经是数组中的最后一个元素了那它肯定是我们要找的如果a[mid]的后一个元素a[mid1]不等于value那也说明a[mid]就是我们要找的最后一个值等于给定值的元素。如果我们经过检查之后发现a[mid]后面的一个元素a[mid1]也等于value那说明当前的这个a[mid]并不是最后一个值等于给定值的元素。我们就更新lowmid1因为要找的元素肯定出现在[mid1, high]之间。
4.3-查找第一个大于等于给定值的元素 对于a[mid]大于等于给定值value的情况我们要先看下这个a[mid]是不是我们要找的第一个值大于等于给定值的元素。如果a[mid]前面已经没有元素或者前面一个元素小于要查找的值value那a[mid]就是我们要找的元素。如果a[mid-1]也大于等于要查找的值value那说明要查找的元素在[low, mid-1]之间所以我们将high更新为mid-1。 /*** 查询数组中查找第一个大于等于给定值的元素返回数组的索引** param array 目前数组* param target 目标值* return 数组下标索引没有查询到返回-1*/private static int binarySearch04(int[] array, int target) {int low 0;int high array.length - 1;while (low high) {int mid low ((high - low) 1);if (array[mid] target) {if ((mid 0) || array[mid - 1] target) {return mid;} else {high mid - 1;}} else {low mid 1;}}return -1;}
4.4-查找最后一个小于等于给定值的元素 对于a[mid]小于等于给定值value的情况我们要先看下这个a[mid]是不是我们要找的最后一个值小于等于给定值的元素。如果a[mid]后面已经没有元素或者后面一个元素大于要查找的值value那a[mid]就是我们要找的元素。如果a[mid1]也小于等于要查找的值value那说明要查找的元素在[mid1, high]之间所以我们将low更新为mid1。 /*** 查询数组中查找最后一个小于等于给定值的元素返回数组的索引** param array 目前数组* param target 目标值* return 数组下标索引没有查询到返回-1*/private static int binarySearch05(int[] array, int target) {int low 0;int maxIndex array.length - 1;int high array.length - 1;while (low high) {int mid low ((high - low) 1);if (array[mid] target) {if ((mid maxIndex) || array[mid 1] target) {return mid;} else {low mid 1;}}}return -1;}
