二分查找(折半查找)算法教学
使用二分查找的好处
在这里我用日常生活举例.比如询问一台电脑的价格,它的价格区间在**(1, 10000)**之间.我们的第一反映肯定是询问价格是超于5000还是低于5000,这样可以排除一半的错误答案,再以此类推,不断砍半.最终会以小于14次折半找到正确答案(2^14^=16384).比1元,2元,3元这种每次加一的询问不知道好多少(现实应该不会遇到这种人).
二分查找在代码中的逻辑(运算过程)
在数组中实现二分查找必须要能满足一个条件--数组是有序数组,像我们的价格一样,从1到10000之间是有序的.
我们假设有这样一个数组
像在日常中询问价格一样,我们需要知道它的价格区间,在这里体现为下标的区间.最左边的下标是0,那么右边的下标怎么计算呢?一个个算不成?
肯定不是,这里我给大家推荐一种方法:函数sizeof
sizeof(arr)算出的是数组的大小,也就是一共有多少个字节.int类型是4个字节,这个数组10个元素,那就是40个字节.用数组的总大小40个字节除以数组一个元素的大小4个字节就能知道数组的元素为10个
这下子我们也就知道了最右边的下标为10-1=9(下标是由0开始的,而元素个数是由1开始的).
然后跟上面的举例一样,我们要知道它的中间值,也就是
然后我们每次要将我们要查找的数字k(假设k=6),跟数组的中间值arr[mid]进行比较.当mid=4时,arr[mid]=5,5 arr[mid])
left = mid + 1;
else
break;
因为在循环中mid的值一直会改变,所以将mid = (left + right) / 2写到循环里面.
循环的判断条件是left
