LEETCODE 35. 搜索插入位置

LEETCODE 35. 搜索插入位置

题解

一般来说在排序数组中查找某个元素,那首先想到的就是用二分查找,这道题也是用了二分查找解决的,但它跟正常的二分查找在细节上有些不同,我们在正常的二分查找基础上稍作修改就可以解决这道题了。
二分查找的思路很简单,但是具体实现的时候,一不小心可能就会出错。

下面我们先看看如何实现一个正确的二分查找
假设有[1,2,3,4,5,6,7,8,9,10,11]这个数组,求目标值targeet=2在数组中的下标,target指向的是绿色的格子,begin=0落在数组左边界上,end=len(arr)-1落在数组右边界上,具体查找过程如下图所示:

首先求出中间下标mid,判断arr[mid]是大于、等于、还是小于target,然后再决定是往数组左半边查找,还是右半边查找,其过程如下:

  1. mid=5arr[mid]>target,减小右边界end
  2. mid=2arr[mid]>target,继续减小右边界end
  3. mid=0arr[mid]<target,增加左边界begin
  4. mid=1,arr[mid]==target,返回

二分查找的开头循环判断是: while begin<=end
这里的循环判断终止条件是一个容易出错的地方。从上图中第四行可以看出,beginmidend三个变量都指向了下标1,如果循环的终止条件写成了while begin<end,那么上述的判断就不对了,程序也就没法返回正确值了。

目标值taget=10,即出现出数组右侧,其处理过程也是类似的。

 

  1. mid=5arr[mid]<target,增加左边界begin
  2. mid=8arr[mid]<target,继续增加左边界begin
  3. mid=9add[mid]==target,返回

二分查找中往数组左边查找的时候是写成end=mid-1,如果改写成end=mid这样可以吗?
请看下面这个例子:
arr=[1,3,5,7]target=2
这样的话,结果应该是返回-1,我们看下执行流程:

  1. begin=0,end=3, mid=1arr[mid]>target
  2. end=mid
  3. begin=0,end=1,mid=0arr[mid]<target
  4. begin=mid
  5. begin=1,end=1,mid=1 死循环….

确定了循环的终止条件,以及如何往左/往右查找,还有一个小细节需要说明下,一般我们取中间值,是这么写 mid = (begin+end)/2
beginend都很大时其结果可能会溢出,所以可以改成这样:
mid = begin+(end-begin)/2

到这里我们就可以写出一个二分查找的模板了

def binarySearch(nums, target):
	if not nums:
		return -1
	begin = 0
	end = len(nums)-1
	while begin&lt;=end:
		mid = begin+(end-begin)/2
		if nums[mid]&gt;target:
			end = mid-1
		elif nums[mid]&lt;target:
			begin = mid+1
		else:
			return mid
	return -1
                                             

当数组中包含了target,上述的代码执行正确,但如果target不在数组中呢?
很简单,等循环退出后,返回begin就可以了:

上图中,要查找的值是7,它不在数组中,于是beginend会不断逼近最终值,不会指向6因为小了,也不会指向9因为大了,最终会落到8上。
这也很好理解,假设有数组[1,2,3....,i-1,i+1,i+2,...]我们要查找的值是imid指向i-1时,比i小,所以继续往数组右边找,当找到i+1时,又比i大,于是再往数组左边找,这时触发了循环终止条件while begin<=end
循环退出后,begin就指向了i+1的位置,而i+1正是我们要找到的位置(将i放到i+1的位置,然后i+1和后面的元素都往右挪一位,整个数组又有序了),所以返回begin即可。

java代码:

class Solution {
	public int searchInsert(int[] nums, int target) {
		if(nums==null) {
			return -1;
		}
		int begin = 0;
		int end = nums.length-1;
		while(begin&lt;=end) {
			int mid = begin+(end-begin)/2;
			if(nums[mid]&gt;target) {
				end = mid-1;
			}
			else if(nums[mid]&lt;target) {
				begin = mid+1;
			}
			else {
				return mid;
			}
		}
		return begin;
	}
}
                                                                  

python代码:

class Solution(object):
	def searchInsert(self, nums, target):
		if not nums:
			return -1
		begin = 0
		end = len(nums)-1
		while begin&lt;=end:
			mid = begin+(end-begin)/2
			if nums[mid]&gt;target:
				end = mid-1
			elif nums[mid]&lt;target:
				begin = mid+1
			else:
				return mid
		return begin
                                                      

(全文完)

7 次阅读

2 thoughts on “LEETCODE 35. 搜索插入位置

发表评论

电子邮件地址不会被公开。