本文共 4360 字,大约阅读时间需要 14 分钟。
如果要在一个有序的数组中,查找某个元素,那么二分查询是一种非常高效的方式,每一次查找都能过滤掉一半的元素,所以时间复杂度为O(logn)。
每次只找到整个数组的中间元素,如果中间元素就是要找的元素则直接返回,否则通过比较中间元素与目标元素的大小来判断,下一次应该在中间元素的右半边查找还是左半边查找,最终重复上述流程,直到找到或者不能再分为止。
假设在一个按照升序排列的数组中,找指定的值所在数组的下标,那我们就可以通过二分的方式查询
public int binarySearch(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { //找到中点,这样写l + ((r - l) >> 1) 等同于 (l+r)/2,但是可以防止l+r溢出 int mid = l + ((r - l) >> 1); //如果等于目标值直接返回 if (nums[mid] == target) { return mid; } //如果中间点大于目标值,则找左半边,否则找右半边 if (nums[mid] > target) { r = mid - 1; } else { l = mid + 1; } } //找不到返回-1 return -1; }
那么是不是一定要在完全有序的数组中才能利用二分查找呢,接下来我们来看看几道非完全有序的数组,是如何使用二分查找的。
以下的题目来自LeetCode
来自leetcode第33题
虽然数组不是完全有序的,但是我们不难发现,通过一次二分后,必然有一半有序的,一半无序的(但是无序的情况依旧能通过二分变为一半有序一半无序),只要符合这样的规律,那么我们就可以依然可以使用二分进行查找。
假设中间点在旋转点的左边,那么中间点左半部分一定是有序的。
假设中间点在旋转点的右边,那么中间点右半部分一定是有序的。public int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + ((r - l) >> 1); if (nums[mid] == target) { return mid; } /** * 如果nums[mid] < nums[r]成立,则表示mid 到 r区间一定是有序的,那么接下来按照有序的方式进行二分查找即可 * 否则表示l 到 mid的区间一定是有序的,那么同样在这个区间也可以按照二分的方式查找即可 */ if (nums[mid] < nums[r]) { //如果nums[mid] < target && target <= nums[r]成立,则在mid到r的范围内找,然后在l到mid的范围找 if (nums[mid] < target && target <= nums[r]) { l = mid + 1; } else { r = mid - 1; } } else { //如果nums[l] <= target && target < nums[mid]成立,则在l到mid的范围内找,然后在mid到r的范围找 if (nums[l] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } } return -1; }
来自leetcode第81题
这题与上一题不同之处在于,允许数组中有重复元素,那么也就意味有可能出现lmidr的情况,在这种情况下,我们就无法区分出哪半边是有序的。下面两张图,都是nums[l] = nums[mid] = nums[r] 的情况,假设目标值在升序的范围中,那么很明显两种升序的范围分别在mid左边和mid右边。
如果遇到这样的情况,我们就让l和r分别向右和向左移动一位,然后再找中间点,直到不满足 lrmid,此时我们就能判断升序到底是在mid的左边还是右边了。
public boolean search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + ((r - l) >> 1); if (nums[mid] == target) { return true; } //如果nums[l] == nums[mid] == nums[r],就让l、r都移动一位。其他逻辑和前一题没有重复的值情况一样 if (nums[l] == nums[mid] && nums[r] == nums[mid]) { l++; r--; } else if (nums[l] <= nums[mid]) { if (nums[l] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { if (nums[mid] < target && target <= nums[r]) { l = mid + 1; } else { r = mid - 1; } } } return false; }
这题与第一题类似,实际上也可以很容易分析出规律
从图中可以看出,当mid指向的下标值小于r指向的下标值时,则最小值一定在mid的右边,反之则一定在mid的左边。public int findMin(int[] nums) { int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + ((r - l) >> 1); /** * 通过不断的比较nums[r] <= nums[mid],最终一定会走到一段排序的范围中, 那么再通过r=mid,使得r无限的靠近最小值,直到二分到最后。 */ if (nums[r] <= nums[mid]) { l = mid + 1; } else { r = mid; } } return nums[r]; }
结合前面几题的套路,这题就比较容易找出规律了,直接上代码,和前一题比无非就是多了一种nums[r] == nums[mid]的情况,按照套路移动一次r的下标即可。
public int findMin(int[] nums) { int l = 0; int r = nums.length - 1; while (l < r) { int mid = l + ((r - l) >> 1); if (nums[r] < nums[mid]) { l = mid + 1; } else if (nums[r] > nums[mid]) { r = mid; } else { r -= 1; } } return nums[r]; }
转载地址:http://ohlrb.baihongyu.com/