Binary Search Template
public int findPostion(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
start = mid;
}
else {
end = mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
Unit 1 Practice I
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.
/* 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 = 1;
int end = n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isBadVersion(mid)) {
end = mid;
}
else {
start = mid;
}
}
if(isBadVersion(start)) {
return start;
}
return end;
}
}
Unit 2 Practice II
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.
Return 6.
/* The guess API is defined in the parent class GuessGame.
@param num, your guess
@return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); */
public class Solution extends GuessGame {
public int guessNumber(int n) {
int start = 1, end = n;
while(start + 1 < end) {
int mid = start + (end - start) / 2;
if(guess(mid) == 0) {
return mid;
} else if(guess(mid) == 1) {
start = mid;
} else {
end = mid;
}
}
if(guess(start) == 1) {
return end;
}
return start;
}
}
Unit 3 Practice III
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
public class Solution {
public int searchInsert(int[] nums, int target) {
if (nums.length == 0 || nums == null) {
return 0;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
start = mid;
}
else {
end = mid;
}
}
if (nums[start] >= target) {
return start;
}
else if (nums[end] >= target) {
return end;
}
else {
return end + 1;
}
}
}
Unit 4 Practice IV
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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) {
return new int[]{-1, -1};
}
int start, end, mid;
int[] bound = new int[2];
// search for left bound
start = 0;
end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
end = mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] == target) {
bound[0] = start;
} else if (nums[end] == target) {
bound[0] = end;
} else {
bound[0] = bound[1] = -1;
return bound;
}
// search for right bound
start = 0;
end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
start = mid;
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (nums[end] == target) {
bound[1] = end;
} else if (nums[start] == target) {
bound[1] = start;
} else {
bound[0] = bound[1] = -1;
return bound;
}
return bound;
}
}
Unit 5 Practice V
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False
public class Solution {
public boolean isPerfectSquare(int num) {
if (num < 1) {
return false;
}
long start = 1;
long end = num;
while (start + 1 < end) {
long mid = start + (end - start) /2 ;
if (mid * mid == num) {
return true;
} else if (mid * mid < num) {
start = mid;
} else {
end = mid;
}
}
if (start * start == num || end * end == num) {
return true;
} else {
return false;
}
}
}
