中间商可以做网站吗,指数基金是什么意思,泰州网站设计哪家好,网站建设培训招生引言: 由于前段时间学习效率不高,导致后面复习前面数据结构没有一个大纲,因此打算重新来学习以下数据结构,期望再次把数据结构学透,并有深刻的印象.并且记录每一次的学习记录 以便于后续复习
二分查找
需求:在有序数组arr内,查找target值
如果找到返回索引位置如果找不到返回…引言: 由于前段时间学习效率不高,导致后面复习前面数据结构没有一个大纲,因此打算重新来学习以下数据结构,期望再次把数据结构学透,并有深刻的印象.并且记录每一次的学习记录 以便于后续复习
二分查找
需求:在有序数组arr内,查找target值
如果找到返回索引位置如果找不到返回 -1
基础版
步骤:
设定两个指针(左闭右闭) 分别为 i 0,j arr.length-1循环条件 ij ,如果ij 结束查找 没找到定义变量 m (ij)/2比较target与m索引的值 (1)target arr[m] — j m-1 (2)target arr[m] — i m1 (3)target arr[m] — return m循环结束没找到 返回-1;
public static int binarySearch(int[] arr,int target){int i 0,j arr.length-1;//设置指针和初始值while(ij){int m (ij)/2;if(targetarr[m]){j m-1;}else if(arr[m]target){i m1;}else{return m;}}return -1;}查找14动态演示
问题一: 循环条件为ij 为什么不是ij? 相当于多了ij 这个条件 ,意味着但ij 时这个元素也要参与比较 比如 查找 5 时 最后 i j m 都会指向5 若没有 就跳出了循环i,j 就没有参与到比较 问题二: (ij) /2 是否有问题? 从客观来讲,没有问题 但是在极端情况下,数据量达到整型的最大值的(ij)就会出现问题 由于计算机存储的数据是有一定的范围的,就有可能会导致算出来的结果为负值 所以要用到位运输 (ij)1 无符号右移可以避免此情况发生 改动版
思维逻辑大概与基础版相似 考虑在算法的优劣 这种方法相当于基础版更优化了一些 public static int binarySearchAlternative(int[] arr,int target){int i 0,j arr.length;//变化一:i 作为查找数据的左闭 而j 只是一个边界不参与运输while (ij){//ij 表示 j下标的运算不用参与计算了int m (ij)1;if (targetarr[m]){j m;//j始终保持为边界} else if (arr[m]target) {i m1}else{return m;}}return -1;}平衡版
在基础版中假设在while 循环中执行了L次 ,那么假设目标元素在最左边 if 就执行L次,而如果元素在最右边,if-else 就执行了2*L次 因此用该方法查找时并不平衡.
public static int binarySearchBalance(int[] arr,int target){int i 0,j arr.length;while(1j-i){int m (ji)1;if(targetarr[m]){j m;}else {i m;}}if(arr[i] target){return i;}else {return -1;}}提示
左闭右开的区间, i 指向可能是目标,而 j 指向的不是目标 是边界不在循环内找出,等范围内只剩下 i 时,退出循环,在循环外比较arr[i]与targert\循环内的平均比较次数减少了时间复杂度为O(log(n)) — 最坏和最好情况下均是
复杂度
时间复杂度:一个算法的执行,随数据规模增大,而增加的时间成本 空间复杂度:一个算法的执行,随数据规模增大,而额外增加的空间成本
两者均用大O表示法,考虑的是最复杂的情况
例如,二分查找的时间复杂度为O(log(n)) 空间复杂度为O(1);
总结
基础版和改动版的区别在于 给定的指针的位置不同 基础版在于 包括 i 索引和j索引的以内包括自身数据查找 为左闭右闭 改动版在于 包括 i 索引到j索引前的数据查找 为左闭右开
