Search in Rotated Sorted Array
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.
难度：medium
Solution: Binary Search
解题思路：
- 根据start，mid和end三个位置的元素大小关系判断pivot的位置：如果nums[start] > nums[mid] && nums[mid] < nums[end]，pivot在左半边；如果nums[start] < nums[mid] && nums[mid] > nums[end]，pivot在右半边。因为pivot只可能在一边，我们其实可以通过判断nums[mid]和nums[end]之间的关系就可以判断pivot的位置。最好是用nums[mid]和nums[end]之间的关系，因为在用nums[mid]和nums[start]的时候有个特殊情况需要处理。
- 在知道pivot的位置之后，通过判断target是否在sorted那部分来用binary search来解决问题。
public class Solution {
public int search(int[] nums, int target) {
int begin = 0, end = nums.length - 1, mid, index = -1;
while(begin <= end) {
mid = begin + ((end - begin) >> 1);
if(nums[mid] == target) {
index = mid;
break;
} else {
if(nums[mid] < nums[end]) {
if(target > nums[mid] && target <= nums[end]) {
begin = mid + 1;
} else {
end = mid - 1;
}
} else {
if(target >= nums[begin] && target < nums[mid]) {
end = mid - 1;
} else {
begin = mid + 1;
}
}
}
}
return index;
}
}
有bug的版本
public class Solution {
public int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while(start <= end) {
int mid = start + ((end - start) >> 1);
if(target == nums[mid]) {
return mid;
} else {
if(nums[mid] > nums[start]) {
if(target < nums[mid] && target >= nums[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else (nums[mid] < nums[start]) { // when start == mid, there's a bug here. Test case: [3, 1] 1
if(target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
}
return -1;
}
}
Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why?
难度：medium
Solution: Binary Search
和上一个题类似，首先要确定pivot的位置，然后判断target可能在哪个部分。但是这个问题中，pivot的位置可能无法判断，这时候就只能顺序搜索！
public class Solution {
public boolean search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while(start <= end) {
int mid = start + ((end - start) >> 1);
if(nums[mid] == target) {
return true;
} else {
if(nums[mid] < nums[end]) {
// pivot is not here
if(target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
} else if(nums[mid] > nums[end]) {
// pivot is here
if(target < nums[mid] && target >= nums[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
// don't know where pivot is
end -= 1; // move the boundary that has been checked
}
}
}
return false;
}
}
Search a 2D Matrix II
Medium
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 in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.
Solution: Divide and Conquer
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int i = 0, j = n - 1;
while(i < m && j >= 0) {
if(matrix[i][j] > target) {
--j;
} else if(matrix[i][j] < target) {
++i;
} else {
return true;
}
}
return false;
}
}
Solution: Binary Search
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int i = 0, j = m - 1;
while(i < j) {
int k = i + ((j - i) >> 1);
int start = 0, end = n - 1;
if(matrix[k][end] == target) {
return true;
} else if(matrix[k][end] < target) {
i = k + 1;
continue;
}
if(matrix[k][start] == target) {
return true;
} else if(matrix[k][start] > target) {
j = k - 1;
continue;
}
break;
}
for(int k = i; k <= j; ++k) {
int start = 0, end = n - 1;
while(start <= end) {
int mid = start + ((end - start) >> 1);
if(matrix[k][mid] == target) {
return true;
} else if(matrix[k][mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return false;
}
}
Search for a Range
Given 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].
难度：medium
Solution: Divide and Conquer (Recursive)
用递归的方法来解决两边都需要搜索的情况，在得到搜索结果之后进行汇总。
public class Solution {
private int[] searchRangeHelper(int[] a, int start, int end, int target) {
int mid;
int[] res = new int[] {-1, -1}, temp;
if(start == end) {
if(a[start] == target) {
res[0] = start;
res[1] = end;
}
} else if(start < end) {
mid = start + (end - start) / 2;
if(a[mid] == target) {
res[0] = mid;
res[1] = mid;
temp = searchRangeHelper(a, start, mid - 1, target);
if(temp[0] != -1) {
res[0] = temp[0];
}
temp = searchRangeHelper(a, mid + 1, end, target);
if(temp[1] != -1) {
res[1] = temp[1];
}
} else if(a[mid] > target) {
res = searchRangeHelper(a, start, mid - 1, target);
} else if(a[mid] < target) {
res = searchRangeHelper(a, mid + 1, end, target);
}
}
return res;
}
public int[] searchRange(int[] nums, int target) {
return searchRangeHelper(nums, 0, nums.length - 1, target);
}
}
Solution: Classic Binary Search (Iterative)
public class Solution {
private void lowerBound(int[] nums, int target, int[] res) {
int start = 0, end = nums.length - 1;
while(start <= end) {
int mid = start + ((end - start) >> 1);
if(nums[mid] > target) {
end = mid - 1;
} else if(nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
res[0] = mid;
}
}
}
private void upperBound(int[] nums, int target, int[] res) {
int start = 0, end = nums.length - 1;
while(start <= end) {
int mid = start + ((end - start) >> 1);
if(nums[mid] < target) {
start = mid + 1;
} else if(nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
res[1] = mid;
}
}
}
public int[] searchRange(int[] nums, int target) {
int[] res = {-1, -1};
lowerBound(nums, target, res);
upperBound(nums, target, res);
return res;
}
}
Search Insert Position
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.
如果target不存在，start指向的位置就是要插入的位置。
Solution: Binary Search
public class Solution {
public int searchInsert(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while(start <= end) {
int mid = start + ((end - start) >> 1);
if(nums[mid] == target) {
return mid;
} else if(nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
}
First Bad Version
Easy
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Solution: Binary Search
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int start = 0, end = n;
while(start < end) {
int mid = start + ((end - start) >> 1);
if(isBadVersion(mid)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
}
Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. You may assume no duplicate exists in the array.
难度：medium
Solution: Binary Search
class Solution {
public int findMin(int[] nums) {
int begin = 0;
int end = nums.length - 1;
while(begin < end) {
int mid = begin + ((end - begin) >> 1);
if(nums[mid] < nums[end]) {
end = mid;
} else {
begin = mid + 1;
}
}
return nums[end];
}
}
Find Minimum in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. The array may contain duplicates.
难度：hard
class Solution {
public int findMin(int[] nums) {
int begin = 0;
int end = nums.length - 1;
while(begin < end) {
int mid = begin + ((end - begin) >> 1);
if(nums[mid] < nums[end]) {
end = mid;
} else if(nums[mid] == nums[end]) { // cannot tell which half side min is on
end -= 1;
} else {
begin = mid + 1;
}
}
return nums[end];
}
}
Find Peak Element
A peak element is an element that is greater than its neighbors. Given an input array where nums[i] != nums[i + 1], find a peak element and return its index. The array may contain peaks, in that case return the index to any one of the peaks is fine. You may imagine that nums[-1] = nums[n] = -∞. Note: your solution should be logarithmic complexity.
难度：medium
Solution: Binary search
class Solution {
public int findPeakElement(int[] nums) {
int begin = 0;
int end = nums.length - 1;
while(begin < end) {
int mid = begin + ((end - begin) >> 1);
if(nums[mid] > nums[mid + 1]) {
end = mid;
} else {
begin = mid + 1;
}
}
return end;
}
}