704.Binary-Search

704. Binary Search

题目地址

https://www.jiuzhang.com/solutions/palindrome-partitioning-ii/

题目描述

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;
}