Comment on page

704.Binary-Search

题目地址

题目描述

Given a string s, cut s into some substrings such that every substring is a palindrome.
​
Return the minimum cuts needed for a palindrome partitioning of s.

代码

public class Solution {
public int binarySearch(int[] array, int target) {
if (array == null || array.length == 0) return -1;
​
int start = 0, end = array.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (array[mid] == target) {
start = mid;
} else if (array[mid] < target) {
start = mid;
} else {
end = mid;
}
}
​
if (array[start] == target) return start;
​
if (array[end] == target) return end;
​
return -1;
}
}
lowerBound:
public int lowerBound(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int lb = -1, ub = nums.length;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (nums[mid] < target) {
lb = mid;
} else {
ub = mid;
}
}
​
return lb + 1;
}
UpperBound:
public int upperBound(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int lb = -1, ub = nums.length;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (nums[mid] > target) {
ub = mid;
} else {
lb = mid;
}
}
​
return ub - 1;
}