# [算法总结] 二分查找

### 1. 最基本的二分查找

```public int binarySearch(int[] A, int target, int n){
int low = 0, high = n, mid;
while(low <= high){
mid = low + (high - low) / 2;
if(A[mid] == target){
return mid;
}else if(A[mid] > target){
high = mid - 1;
}else{
low = mid + 1;
}
}
return -1;
}```

leetcode参考：Search Insert Position

### 2. 查找目标值区域的左边界/查找与目标值相等的第一个位置/查找第一个不小于目标值数的位置

A = [1,3,3,5, 7 ,7,7,7,8,14,14] target = 7 return 4

```public int binarySearchLowerBound(int[] A, int target, int n){
int low = 0, high = n, mid;
while(low <= high){
mid = low + (high - low) / 2;
if(target <= A[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}
if(low < A.length && A[low] == target)
return low;
else
return -1;
}```

### 3. 查找目标值区域的右边界/查找与目标值相等的最后一个位置/查找最后一个不大于目标值数的位置

A = [1,3,3,5,7,7,7, 7 ,8,14,14] target = 7 return 7

```public int binarySearchUpperBound(int[] A, int target, int n){
int low = 0, high = n, mid;
while(low <= high){
mid = low + (high - low) / 2;
if(target >= A[mid]){
low = mid + 1;
}else{
high = mid - 1;
}
}
if(high >= 0 && A[high] == target)
return high;
else
return -1;
}```

### 4. 查找最后一个小于目标值的数/查找比目标值小但是最接近目标值的数

A = [1,3,3, 5 ,7,7,7,7,8,14,14] target = 7 return 3

```int low = 0, high = n, mid;
while(low <= high){
mid = low + (high - low) / 2;
if(target <= A[mid]){
high = mid - 1;
}else{
low = mid + 1;
}
}
return high < 0 ? -1 : high;```

### 5. 查找第一个大于目标值的数/查找比目标值大但是最接近目标值的数

A = [1,3,3,5,7,7,7,7, 8 ,14,14] target = 7 return 8

```int low = 0, high = n, mid;
while(low <= high){
mid = low + (high - low) / 2;
if(target >= A[mid]){
low = mid + 1;
}else{
high = mid - 1;
}
}
return low > n ? -1 : low;```

### 6. 旋转数组返回最小元素

#### 6.1 查找旋转数组的最小元素（假设不存在重复数字）

LeetCode: Find Minimum in Rotated Sorted Array Input: [3,4,5,1,2] Output: 1

```public int findMin(int[] nums) {
int len = nums.length;
if(len == 0)
return -1;
int left = 0, right = len - 1, mid;

while(left < right){
mid = left + (right - left) / 2;
if(nums[mid] > nums[right])
left = mid + 1;
else{
right = mid;
}
}
return nums[left];
}```

• 如果`nums[mid] > nums[right]`，说明前半部分是有序的，最小值在后半部分，令`left = mid + 1`
• 如果`nums[mid] <= num[right]`，说明最小值在前半部分，令`right = mid`

#### 6.2 查找旋转数组的最小元素（存在重复项）

LeetCode: Find Minimum in Rotated Sorted Array II 剑指offer：旋转数组的最小数字 Input: [2,2,2,0,1] Output: 0

```public int findMin(int[] nums) {
int len = nums.length;
if(len == 0)
return -1;
int left = 0, right = len - 1, mid;
while(left < right){
mid = left + (right - left) / 2;
if(nums[mid] > nums[right])
left = mid + 1;
else if(nums[mid] < nums[right])
right = mid;
else
right--;
}
return nums[left];
}```

### 7. 在旋转排序数组中搜索

#### 7.1 不考虑重复项

LeetCode: Search in Rotated Sorted Array

• 先利用方法 6.1 查找数组中的最小元素，即确定分界点的位置
• 把旋转的数组当成偏移，用`(offset + mid) % len`来求真实的 mid 的位置。
• 然后用二分查找来定位目标值
```public int search(int[] nums, int target) {
int len = nums.length;
if(len == 0)
return -1;
int left = 0, right = len - 1, mid;
while(left < right){
mid = left + (right - left) / 2;
if(nums[mid] > nums[right])
left = mid + 1;
else
right = mid;
}
int offset = left;
left = 0;
right = len - 1;
while(left <= right){
mid = left + (right - left) / 2;
int realmid = (mid + offset) % len;
if(nums[realmid] == target)
return realmid;
else if(nums[realmid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}```

```public int search(int[] nums, int target) {
int len = nums.length;
if(len == 0)
return -1;
int left = 0, right = len - 1, mid;
while(left <= right){
mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if(nums[left] <= nums[mid]){
if(target < nums[mid] && target >= nums[left])
right = mid - 1;
else
left = mid + 1;
}else if(nums[mid] <= nums[right]){
if(target > nums[mid] && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}```

#### 7.2 存在重复项

LeetCode: Search in Rotated Sorted Array II

```public boolean search(int[] nums, int target) {
int len = nums.length;
if(len == 0)
return false;
int left = 0, right = len - 1, mid;
while(left <= right){
mid = left + (right - left) / 2;
if(nums[mid] == target)
return true;
else if(nums[mid] > nums[right]){
if(target < nums[mid] && target >= nums[left])
right = mid;
else
left = mid + 1;
}else if(nums[mid] < nums[right]){
if(target > nums[mid] && target <= nums[right])
left = mid + 1;
else
right = mid;
}else{
right --;
}
}
return false;
}```

### 8. 二维数组中的查找

• 当要查找数字比右上角数字大时，下移；
• 当要查找数字比右上角数字小时，左移；

0 条评论

• ### ［LeetCode］Degree of an Array 数组的度 ［LeetCode］Degree of an Array 数组的度

链接：https://leetcode.com/problems/degree-of-an-array/description/ 难度：Easy 题目：69...

• ### [剑指offer] 数字在排序数组中出现的次数

正常的思路就是二分查找了，我们用递归的方法实现了查找k第一次出现的下标，用循环的方法实现了查找k最后一次出现的下标。 除此之外，还有另一种奇妙的思路，因为da...

• ### ［LeetCode］Longest Continuous Increasing Subsequence 最长连续增长序列 ［LeetCode］Longest Continuous Incr

链接：https://leetcode.com/problems/longest-continuous-increasing-subsequence/descr...

• ### LeetCode-15-3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b ...

• ### 漫画：知乎面试题（旋转数组最小值Ⅱ - 进阶版）

今天是小浩算法“365刷题计划”第72天。继续为大家讲解二分法系列篇 - 旋转排序数组最小值Ⅱ（进阶版）。话不多说，直接看题：

• ### 打卡群刷题总结0727——搜索旋转排序数组 II

链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii

• ### [Leetcode][python]Sort Colors/颜色分类

给出一个由红、白、蓝三种颜色组成的数组，把相同颜色的元素放到一起，并整体按照红、白、蓝的顺序。用0表示红色，1表示白色，2表示蓝色。这题也称为荷兰国旗问题。

• ### 《剑指 offer》 21. 调整数组顺序使奇数位于偶数前面

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 21.调整数组顺序使奇数位于偶数前面，这道题目既可以使用 首尾双指针，也可以使用 快...

• ### 【Leetcode】81. 搜索旋转排序数组 II

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

• ### Leetcode 153. Find Minimum in Rotated Sorted Array

版权声明：博客文章都是作者辛苦整理的，转载请注明出处，谢谢！ https://blog.csdn....