雅乐网

计算机技术、学习成长

编程 » OJ刷题 » 【OJ】二分查找、旋转数组查找、二分查找变种

【OJ】二分查找、旋转数组查找、二分查找变种

二分查找是分治算法的经典应用,它可以每次把问题的规模减少一半,从而在log的时间内找到结果。

二分查找

二分查找适用于有序数组的查找,它的核心思想是,选取一个数组中间的数字a[mid] 和要查找的数字 target 进行比较,如果target小于中间数字,则可以排除右半部分;如果target大于中间数字,可以排除左半部分。

二分查找的典型代码如下,若查找到,返回对应元素下标,否则返回-1 。

旋转数组查找

Search in Rotated Sorted Array | LeetCode OJ

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

这里的旋转数组,其实就是一个升序数组循环右移后形成的,数组的样子大概如下图所示:

虽然整体不是有序的了,但毕竟是从有序变化而来,旋转数组中,左半部分是大于右半部分的,而且两个部分是各自有序的。

可以用二分查找的方法,比较中间元素和目标target 。不同的是,此时我们要考虑中间数字是位于旋转数组的左半部分还是右半部分。

1. target  < a[mid] 时,

1.1 如果mid位于旋转数组的左半部分 那么小于a[mid]的元素分布在左右两部分都有(绿色)

而且这两个部分也是有序的,左半部分的大于右半部分。此时需要判断target和左半部分第一个元素,就可以确定target是在左边还是右边。

1.1.1 如果target >= a[start] 则target在左半部分.

1.1.2 如果target < a[start] 则target在右半部分

1.2 如果mid位于旋转数组的右半部分 此时旋转数组中小于a[mid]的元素均位于左侧

2. target  > a[mid] 时,情况也是类似的。

代码:

二分查找变种

有重复元素

Search for a Range | LeetCode OJ

iven an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

这个问题可以分解为2个二分查找的问题:当待查找的数字在数组中有多个时,一个版本返回其中最前面的下标,一个版本返回最后面的下标。

先来看第一个版本,我们需要返回数组中大于target的第一个元素的下标。例如:数组[0, 2, 2, 3],查找-1返回0,查找0返回1,查找1返回1,查找2返回3,查找3返回4,查找4返回4

先上代码:

可以使用循环不变式来理解这段代码为什么会返回大于target的第一个元素的下标:

下面使用n表示数组a的大小。使用数学中的区间表示,[0, low)表示前闭后开区间,不包括a[low];[ high, n )是前开后闭区间,包括a[high]

这里的不变式是,数组a中,[0, low)中的元素的值 <=x ;[ high, n )中的元素的值 >x 。

循环开始前,low=0, high=n ,是朴素的空区间的情况,不变式是成立的。即[0,0)中元素<=x 成立,[n,n)的元素>x也成立。

在每一次循环时,有两种情况:

1. 当x<a[mid]时,high=mid 。[ high, n )中的元素的值 >x 仍然成立;

2. else的情况,x>=a[mid],此时low=mid+1 ,[0, low) 中的元素的值 <=x 仍然成立(也就是区间[0,mid])。

循环结束后,low==high ,不变式仍成立:[0,low) 中元素<=x ;[low, n)元素 > x 。这时a[low]就是大于x的第一个元素。

再来看返回数组中小于target的最后一个元素的下标的代码:

这里的循环不变式是:

[0,low) 中的元素的值 <x

[high,n)中的元素的值 >=x

循环结束后,low是>=x中的元素中的最小的。因此low-1就是<x的元素中的最大的。

Leetcode的代码:

查找插入位置

Search Insert Position | LeetCode OJ

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

这个只要使用上面的search_before的代码,返回大于等于x的第一个元素的下标就可以了

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/oj_bineary_search_and_rotate_array_search.html

上一篇:

下一篇:

我要评论

验证码*: 8 + 5 =