Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
注意这里对二维数组维度的取值，还有在二分查找中中间点，对中间点取值的定位，以及两边缩进的处理的终止条件。
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0 or len(matrix[0]) == 0: return False
row, col = len(matrix), len(matrix[0])
l = 0
r = row * col - 1
while (not l == r):
mid = (l + r - 1) / 2
if (matrix[mid/col][mid%col] < target): #边界关系中，如果这边是小于目标值的，那么可以位置加一；如果是大于等于目标值的，位置保持。
l = mid + 1
else:
r = mid
return matrix[r/col][r%col] == target
Given a sorted array of integers, 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].
非二分法的解法很简单，只要遍历一遍数组，标记下起始和终止位置即可。
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n1, n2 = -1, -1
first = False
for i in range(len(nums)):
if nums[i] == target and first == False:
n1, n2 = i, i
first = True
elif nums[i] == target:
n2 = i
else:
pass
return [n1,n2]
使用二分法，注意怎样寻找左边第一个和右边最后一个。 class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
i,j = 0, len(nums) - 1
left, right = -1, -1
while (i < j):
mid = (i + j)/2
if nums[mid] < target:
i = mid + 1
else:
j = mid
if (nums[i] != target): return [left, right]
left = i
j = len(nums) - 1
while (i < j):
mid = (i + j)/2 + 1
if nums[mid] > target:
j = mid - 1
else:
i = mid
right = j
return [left, right]
Implement int sqrt(int x).
Compute and return the square root of x.
按照二分查找的思路来做，在起始位置上可以做一些剪裁。
public int sqrt(int x) {
if (x == 0)
return 0;
int left = 1, right = Integer.MAX_VALUE;
while (true) {
int mid = left + (right - left)/2;
if (mid > x/mid) {
right = mid - 1;
} else {
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
}
}
}
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
这道题要看透其本质，这里使用的方法是，先加入目标，然后排序，最后查找。这样囊括了所有情况。
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums = set(nums)
nums.add(target)
nums = list(nums)
nums = sorted(nums)
print nums
i, j = 0, len(nums) - 1
while(i < j):
mid = (i+j)/2
if (nums[mid] < target):
i = mid + 1
else:
j = mid
return i
Suppose a sorted array 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.
先考虑没有轮转的数组，在考虑轮转的步数。
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums2 = sorted(nums)
i, j = 0, len(nums2)-1
while(i < j):
mid = (i+j)/2
if (nums2[mid] < target):
i = mid+1
else:
j = mid
if not nums2[i] == target:
return -1
tmp = nums2[0]
pos = -1
for k in nums:
pos = pos + 1
if tmp == k:
break
return (i + pos)%len(nums)