二分查找算法精讲：边界条件与变体问题（左闭右闭 vs 左闭右开）

一.算法描述二.算法实现package com.algorithm.binarysearch; public class BinarySearch { /*params:a - 待查找的升序数组 target - 待查找的目标值 Returns 找到则返回索引 找不到则返回-1 * */ public static int binarySearch(int[] a,int target){//设置元素个数数组和待查找的目标值 int i 0,j a.length - 1;//设置指针和初值 while(ij){ int m (ij) 1; //用无符号右移运算符防止溢出 if(target a[m]){//目标值在中间值左边的情况下 j m - 1; }else if(target a[m]){//目标值在中间值右边的情况下 i m 1; }else { return m; //找到中间值 } } return -1;//找不到的情况下返回-1 } }package com.algorithm.binarysearch; public class BinarySearch { /*params:a - 待查找的升序数组 target - 待查找的目标值 Returns 找到则返回索引 找不到则返回-1 * */ public static int binarySearch(int[] a,int target){//设置元素个数数组和待查找的目标值 int i 0,j a.length;//设置指针和初值 while(ij){ int m (ij) 1; //用无符号右移运算符防止溢出 if(target a[m]){//目标值在中间值左边的情况下 j m; }else if(target a[m]){//目标值在中间值右边的情况下 i m 1; }else { return m; //找到中间值 } } return -1;//找不到的情况下返回-1 } }三.查找问题问题一q为什么是ij意味着区间内有未比较元素而不是ij?s:ij 它们指向的元素也会参与比较。问题二q:ij/2有没有问题s:同一个二进制数在java中会把第一位看作符号位所以用无符号右移运算符防止溢出。问题三q:在比较中写成“”小于符号有何好处s:数组是升序排列的写成小于符号可以是和数组升序排列方向一致不然会很别扭。四.如何判断算法好坏1.时间复杂度含义是用来衡量一个算法的执行随数据规模增大而增长的时间成本。2.如何表示时间复杂度假设算法要处理的数据规模是n代码总的执行行数用函数fn来表示例如:线性查找算法的函数f(n) 3*n3二分查找算法的函数f(n) (floor(log2(n)1)*54渐进上界代表算法执行的最差情况渐进下界代表算法执行的最好情况渐进紧界既能代表算法执行的最好情况也能代表算法执行的最差情况3.常见的大O表示法4.空间复杂度与时间复杂度类似一般也是用大O表示法来衡量一个算法执行随数据规模增大而增长的额外空间成本。5.二分查找性能五.插入数组将数组中没有的元素插入进去六.寻找最侧边元素1.寻找最左侧元素package com.algorithm.binarysearch; public class BinarySearch { /*params:a - 待查找的升序数组 target - 待查找的目标值 Returns 找到则返回索引 找不到则返回-1 * */ public static int binarySearch(int[] a,int target){ int i 0,j a.length - 1; int candidate -1//表示没有任何候选者 while(ij){ int m (ij) 1; if(target a[m]){ j m - 1; }else if(target a[m]){ i m 1; }else { //记录侯选位置 condidate m; j m - 1; } } return -1; }2.寻找最右侧元素package com.algorithm.binarysearch; public class BinarySearch { /*params:a - 待查找的升序数组 target - 待查找的目标值 Returns 找到则返回索引 找不到则返回-1 * */ public static int binarySearch(int[] a,int target){ int i 0,j a.length - 1; int candidate -1//表示没有任何候选者 while(ij){ int m (ij) 1; if(target a[m]){ j m - 1; }else if(target a[m]){ i m 1; }else { //记录侯选位置 condidate m; i m 1; } } return condidate; }