二分查找算法
一、什么是二分查找?
周一早上,天刚蒙蒙亮,程序员小王来到公司,打开电脑,准备一天充实的工作,测试妹子余光中看见小王打开电脑,高兴的跑过来,问小王,今天发型好飘逸呀,测试妹子心想,小王之前没头发,今天怎么有头发了,肯定是植发去了,嘿嘿。小王,嘴角微微上扬优雅的说,周末出去玩,看见假发打折,所以入手了一头,小王说,这个假发不到100块钱,你猜猜多少钱呀,测试妹子说50,小王说低了,再猜,测试妹子说80,小王说高了,再猜,测试妹子说70,小王说,你真聪明,猜对了,就是70,测试妹子在小王的夸赞中高兴的离开了。
小王跟测试妹子玩猜猜游戏其实就是二分查找的思想,二分查找就是在一组有序元素列表中通过对半查找,来快速锁定目标数据。
二、二分查找的运行时间
从组数[1,3,4,5,7,8,10,12] 需要找出target=10 在数组中位置,我们采用一下两种方法就行对比。
第一种方法:遍历数据,找出10在数据中的位置,需要7次,如果目标数在数组的最后一位,最差需要遍历8次,也就是说最差我们需要遍历数组长度次。
第二种方法:二分查找,每次找到中间位置的元素,跟目标数作对比,如果中间元素小于目标数,left=mid+1,如果中间元素大于目标数,right=mid-1,依次类推,直到,left<=right,查找完成。如下图
找出目标元素最差需要3次。
接下来如果我们把数据量放大到10亿条数据,第一种方法最差就需要10亿次,但是二分查找只需要大概30次,这个差距是非常大的,也就是说包含n个元素的列表,使用二分查找最多需要㏒₂n次。
在算法中,算法的好坏,我们采用大O表示法,他代表在最糟糕的情况下灌入算法的数据跟时间的一个关系
第一种方法运行时间O(n),第二种方法运行时间O(㏒₂n)
三、二分查找的练习
leetcode上二分查找题目有两百多道,如果时间足够多,我们可以刷一遍,但是,最终还是要静下心来,真正理解二分查找,学会灵活应用才算是整的掌握了该算法。
35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。输入: nums = [1,3,5,6], target = 5 输出: 2public int searchInsert(int[] nums, int target) { int length = nums.length; int left = 0; int right = nums.length-1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] < target) { left=mid+1; }else{ right=mid-1; } } return left; }
四、总结
1、有序的元素列表
2、时间复杂度㏒₂n