public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left + 1 < right:
mid = int(left + (right - left) / 2)
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid
else:
right = mid
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
Find first "T" in the array, when meet the situation below, still move L pointer:
# F F F T T T
# [1, 2, 10, 11.., n]
def firstBadVersion(self, n):
L = 1
R = n
while L < R:
mid = (L + R) // 2
if isBadVersion(mid) :
R = mid
else:
L = mid + 1
return L
when nums[mid] > nums[mid - 1] means it is on upslope, move L pointer. Otherwise move R pointer.
def findPeakElement(self, nums: List[int]) -> int:
L = 0
R = len(nums)
while L < R:
mid = (L + R) // 2
if mid < len(nums) - 1 and nums[mid + 1] >= nums[mid]:
L = mid + 1
else :
R = mid
return L
Find the first position and the last position separately. Treat differently as nums[mid] == target
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0 || target > nums[nums.length - 1]) {
return new int[]{-1, -1};
}
int left = binarySearchFirst(nums, 0, nums.length - 1, target);
int right = binarySearchLast(nums, 0, nums.length - 1, target);
return left == -1 ? new int[]{-1, -1} : new int[]{left, right};
}
private int binarySearchFirst(int[] nums, int left, int right, int target) {
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid;
}
}
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
private int binarySearchLast(int[] nums, int left, int right, int target) {
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid;
} else {
right = mid;
}
}
if (nums[right] == target) return right;
if (nums[left] == target) return left;
return -1;
}
Use right most digit as a pivot to determine if mid is on the lower side or the higher side, then determine the position of target to move the pointers.
def search(self, nums: List[int], target: int) -> int:
if len(nums) == 0:
return -1
L = 0
R = len(nums) - 1
pivot = nums[R]
while L + 1 < R:
mid = (L + R) // 2
if nums[mid] <= pivot:
if target <= pivot and target >= nums[mid]:
L = mid
else :
R = mid
else :
if target > pivot and target < nums[mid]:
R = mid
else:
L = mid
if nums[L] == target :
return L
if nums[R] == target:
return R
return -1
When nums[mid] == nums[L] and nums[mid] == nums[R] means all three pointers are on same level. Compare target vs nums[R], check if nums[mid] is in between, or on the opposite side.
def search(self, nums: List[int], target: int) -> bool:
L = 0
R = len(nums) - 1
if len(nums) == 0:
return False
while L + 1 < R:
mid = (L + R) // 2
if nums[mid] == target:
return True
if nums[mid] == nums[L] and nums[mid] == nums[R]:
L += 1
R -= 1
elif target <= nums[R]:
if nums[mid] > target and nums[mid] <= nums[R]:
R = mid
else:
L = mid
else:
if nums[mid] < target and nums[mid] > nums[R]:
L = mid
else:
R = mid
if nums[L] == target or nums[R] == target:
return True
return False
Use right most element as pivot to determine the direction of the search. If nums[mid] less and equal to pivot, then move R to mid. Otherwise move L to mid.
def findMin(self, nums: List[int]) -> int:
L = 0
R = len(nums) - 1
pivot = nums[len(nums) - 1]
while L + 1 < R:
mid = (L + R) // 2
if nums[mid] > pivot:
L = mid
else:
R = mid
return min(nums[L], nums[R])
Define boundaries by expanding right pointer. To keep logarithmic time complexity, let's extend it twice as far: right = right * 2. Then binary search.
def search(self, reader, target):
R = 1
while reader.get(R) <= target:
R *= 2
L = 0
while L + 1 < R:
mid = (L + R) // 2
if reader.get(mid) == target:
return mid
if reader.get(mid) < target:
L = mid
else:
R = mid
if reader.get(L) == target:
return L
if reader.get(R) == target:
return R
return -1
Another solution (if getNumber() API is provided):
public boolean binarysearch(long target) {
long start = 0;
long end = 1;
while (getNumber(end) <= target && end < Long.MAX_VALUE / 2) {
end *= 2;
}
if (getNumber(end) < target) {
end = Long.MAX_VALUE;
}
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (getNumber(mid) == target) {
return true;
} else if (getNumber(mid) < target) {
start = mid;
} else {
end = mid;
}
}
return getNumber(start) == target || getNumber(end) == target;
}
2 ^ 10 = 4 ^ 5 = 16 ^ 2 * 4
T: O(logn) S: O(1)
public double myPow(double x, int n) {
if (n == 0) return 1.0;
if (n == 1) return x;
int i = Math.abs(n);
double res = 1.0;
while (i != 0) {
if (i % 2 != 0) {
res *= x;
}
x *= x;
i /= 2;
}
return n < 0 ? 1.0 / res : res;
}
For example, in [1,1,3,3,4,4,5,8,8], elements before 5 keep [even, odd] pattern, to make sure that even and odd number sequence. The elements after 5 break this sequence. In this case, we can determine the target is on the left or the right side of pivot.
def singleNonDuplicate(self, nums: List[int]) -> int:
L = 0
R = len(nums) - 1
while L < R:
mid = (L + R) // 2
if mid % 2 == 0 and mid < len(nums) - 1 and nums[mid + 1] == nums[mid]:
L = mid + 1
elif mid % 2 == 1 and mid > 0 and nums[mid - 1] == nums[mid]:
L = mid + 1
else:
R = mid
return nums[L]
nums[mid] - nums[left] is the number difference on array, mid - leftis the difference of indices. The difference diff between those two numbers can give you how close are we reaching out to k.
The k needs to decrement by diff when moving left pointer, as k is from the beginning.
The result is nums[left] + k. However the number may exceed right so the result is nums[left] + k + 1 in that situation.
public int missingElement(int[] nums, int k) {
int left = 0, right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
int diff = nums[mid] - nums[left] - (mid - left);
if (diff < k) {
left = mid;
k -= diff;
} else {
right = mid;
}
}
if (nums[left] + k >= nums[right]) return nums[left] + k + 1;
return nums[left] + k;
}
dp is an array storing the smallest tail of all increasing subsequences with length i+1 in dp[i].
For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:
len = 1 : [4], [5], [6], [3] => tails[0] = 3
len = 2 : [4, 5], [5, 6] => tails[1] = 5
len = 3 : [4, 5, 6] => tails[2] = 6
We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.
Each time we only do one of the two:
if x is larger than all tails, append it, increase the size by 1
if dp[i-1] < x <= dp[i], update dp[i]
T: O(nlogn)
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int size = 0;
for (int num : nums) {
int L = 0, R = size;
while (L < R) {
int mid = L + (R - L) / 2;
if (res[mid] < num) {
L = mid + 1;
} else {
R = mid;
}
}
res[L] = num;
if (L == size) size++;
}
return size;
}
Count the votes and derive the winner that that time. When querying, store the results in a TreeMap to get the results. Otherwise we can store by using an array and use binary search to find the answer.
TreeMap<Integer, Integer> results;
public TopVotedCandidate(int[] persons, int[] times) {
Map<Integer, Integer> votes = new HashMap<>();
results = new TreeMap<>();
int n = persons.length;
int max = 0, maxperson = -1;
for (int i = 0; i < n; i++) {
votes.put(persons[i], votes.getOrDefault(persons[i], 0) + 1);
if (votes.get(persons[i]) >= max) {
max = votes.get(persons[i]);
maxperson = persons[i];
}
results.put(times[i], maxperson);
}
}
public int q(int t) {
int key = results.get(t) != null ? t
: results.lowerKey(t);
return results.get(key);
}
List<Node> list = new ArrayList<>();
public TopVotedCandidate(int[] persons, int[] times) {
Map<Integer, Integer> votes = new HashMap<>();
int n = persons.length;
int max = 0, maxperson = -1;
for (int i = 0; i < n; i++) {
votes.put(persons[i], votes.getOrDefault(persons[i], 0) + 1);
if (votes.get(persons[i]) >= max) {
max = votes.get(persons[i]);
maxperson = persons[i];
}
list.add(new Node(times[i], maxperson));
}
}
public int q(int t) {
int left = 0, right = list.size() - 1;
if (t > list.get(right).time) {
return list.get(right).maxperson;
}
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (list.get(mid).time == t) return list.get(mid).maxperson;
if (list.get(mid).time < t) {
left = mid;
} else {
right = mid;
}
}
if (list.get(right).time == t) return list.get(right).maxperson;
return list.get(left).maxperson;
}
class Node {
int time;
int maxperson;
Node(int t, int p) {
this.time = t;
this.maxperson = p;
}
}
Store the array to prefix sum and randomly get an integer between range 0 and max. Use binary search to get the index of that integer is presum.
int[] w;
Random rand;
public Solution(int[] w) {
this.w = w;
for (int i = 1; i < w.length; i++) {
w[i] += w[i - 1];
}
this.rand = new Random();
}
public int pickIndex() {
int index = rand.nextInt(w[w.length - 1]) + 1;
int L = 0, R = w.length - 1;
while (L < R) {
int mid = L + (R - L) / 2;
if (w[mid] == index) return mid;
if (w[mid] < index) {
L = mid + 1;
} else {
R = mid;
}
}
return L;
}
We can use Binary Search to find a median of two sorted array. The index i in the first array has to follow this relation as i + j = (len1 + len2) / 2 (Actually it is i + j - 1= (len1 + len2 + 1) / 2). Therefore, use binary search to find the position which nums1[i] >= nums2[j - 1].
You will have i, j. Before return, determine if any of the indices are out of bound. Keep the boundary elements by choosing one value between i and j. If is odd total length, only pick one element as median, otherwise get the average of those two boundary elements.
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
if (len1 > len2) return findMedianSortedArrays(nums2, nums1);
int len = (len1 + len2 + 1) / 2;
int left = 0, right = len1;
while (left < right) {
int m1 = left + (right - left) / 2;
int m2 = len - m1;
if (nums1[m1] < nums2[m2 - 1]) {
left = m1 + 1;
} else {
right = m1;
}
}
int m1 = left, m2 = len - m1;
int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],
m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
if ((len1 + len2) % 2 == 1) return c1;
int c2 = Math.min(m1 >= len1 ? Integer.MAX_VALUE : nums1[m1],
m2 >= len2 ? Integer.MAX_VALUE : nums2[m2]);
return (c1 + c2) / 2.0;
}
public int findInMountainArray(int target, MountainArray A) {
int left = 0, right = A.length() - 1;
// Find the peak index
while (left < right) {
int mid = left + (right - left) / 2;
if (A.get(mid) < A.get(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
int peak = left;
// Binary search on increasing subarray
left = 0;
right = peak;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A.get(mid) < target) {
left = mid + 1;
} else if (A.get(mid) > target) {
right = mid - 1;
} else {
return mid;
}
}
// Binary search on decreasing subarray
left = peak;
right = A.length() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A.get(mid) < target) {
right = mid - 1;
} else if (A.get(mid) > target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
Binary search is a search algorithm usually used on a sorted sequence to quickly find an element with a given value. In this problem we will evaluate how binary search performs on data that isn't necessarily sorted. An element is said to be binary searchable if an element can be found provided the pivot is chosen everytime as the middle element - like in a regular binary search.
We need to find total number of elements which are binary searchable.
Example 1:
[2, 1, 3, 4, 6, 5] - 3 is searchable, 2 is searchable, 1 not searchable, 6 is searchable, 4 is seachable, 5 is not searchable
Output: 4
Example 2:
Input: [1, 3, 2]
Output: 2
Explanation: 3 and 1 are searchable - you look for 3 - find it in the middle, look for 1 - you search the left half....search for 2, you look for it in the left half but didn't find.
Pretend the array is a binary search tree, DFS/BFS all pivot elements and keep track of lower and upper bound for the left and right children. The idea is to figure out how many middle elements in the given start to end range is properly positioned compared to previous middle element - so that they can be binary searchable in the given array.
public int getSearchableCount(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return getSearchableCount(arr, 0, arr.length-1, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private int getSearchableCount(int[] arr, int start, int end, int lowerBound, int upperBound) {
if (start > end) {
return 0;
}
int mid = (start + end) / 2;
int count = 0;
if (arr[mid] >= lowerBound && arr[mid] <= upperBound) count ++;
return count + getSearchableCount(arr, start, mid-1, lowerBound, Math.min(arr[mid], upperBound)) +
getSearchableCount(arr, mid + 1, end, Math.max(arr[mid], lowerBound), upperBound);
}
public static void main(String[] args) {
BinarySearchable obj = new BinarySearchable();
System.out.println(obj.getSearchableCount(new int[]{2, 1, 3, 4, 6, 5}));
System.out.println(obj.getSearchableCount(new int[]{1, 3, 2}));
System.out.println(obj.getSearchableCount(new int[]{1, 2, 2, 3}));
System.out.println(obj.getSearchableCount(new int[]{4, 9, 5, 1, 1}));
}
