> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/binary-search/704.binary-search.md).

# 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.
```

## 代码

```java
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:

```java
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:

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