Classical Binary Search
经典二分查找适用于不包含重复元素的有序数组。二分查找每次取中间值,然后和目标值比较。若中间值大于目标值,则表示目标值在前半部分,反之则在后半部分。然后重复上述过程,直到找到目标值位置,或者遍历所有元素。
代码如下:
|
|
当我第一次写时,将 while
循环中的条件设为 start<end
,实际运行发现某些情况会进入死循环。当数组中不包含目标值时,最后变量之间的关系为 start+1=end
mid=start
,所以会一直在 while
中循环,无法跳出。
First Position of Target
问题:
给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2
因为数组中有重复元素,所以发现目标值时并不能直接返回。当发现中间值时与目标值相等时,有两种情况:
- 中间值正好是首次出现,也就是说重复的目标值都在中间值后面而不是前面
如 1223
第一次取中间值正好取到 2 ,此时元素位置为 1,正好满足要求
- 中间值前面还有重复的目标值
如 12223
第一次取中间值时同样为 2,元素位置为 2,但是这并不是 2 第一次出现的位置。
因此,当发现中间值与目标值相等时,我们默认为上文中的第 2 中情况,也就是说将 end = mid
,当循环完成时,需要进行二次判断,首先判断 start
,然后判断 end
,因为 start
和 end
位置的元素都有可能与目标值相等。
代码如下:
|
|
Last Position of Target
问题:给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target最后一次出现的下标(从0开始),如果target不存在于数组中,返回-1
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回3
这个问题与上个类似,当找到一个数与目标值相等时,只需查找后半段是否还有满足题意的数,将 start = mid
。最后先判断 end
位置的数,然后再判断 start
位置。
代码如下:
|
|
Closest Number in Sorted Array
问题:
在一个有序数组中,给定一个target,要求在数组中找到离target最近的数。
Given [1, 4, 6] and target = 3, return 1.
Given [1, 4, 6] and target = 5, return 1 or 2.
Given [1, 3, 3, 4] and target = 2, return 0 or 1 or 2.
先使用经典二分查找 target,最后再判断距离最近的数
代码如下:
|
|
Total Occurrence of Target
问题:
求有序数组中某个target出现了多少次
利用 Python 内置函数直接判断:
|
|
利用二分法,先查找 target 第一次出现的位置,然后从第一次出现的位置开始遍历列表。
|
|
以上所有源代码链接:https://github.com/ianxin/Algorithm/tree/master/src