总目录：地址如下看总纲
1、介绍【前提有序】
二分查找又称折半查找，既从中间数开始找，然后根据比较结果，选择需要折半的一边出发，
再次折半，以此类推找出元素
2、设计思路（单数）
- 、确定当前数组的下标 mid = (left + right)/2;
- 、其次让需要查找的数 findVal 和 arr[mid] 比较
(1) findVal > arr[mid] 说明要查找的数在 mid 右边，因此向右递归查找
(2) findVal < arr[mid] 说明要查找的数在 mid 左边，因此向左递归查找
(3) findVal = arr[mid] 说明找到，既返回- 、需要注意何时结束递归？
(1)找到就结束
(2)递归完整个数组，仍然没有找到 findVal，也需要结束递归 ，当 left > rigth 就是结束递归的条件
3、代码(单数版）：只返回一个
/**
* 二分查找(单数版)
*
* @param arr 原始数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找的值
* @return
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
// 当 left > right 时候，说明已经递归完毕，仍没有找到
if (left > right) {
return -1;
}
// 折半，取值
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) {// 向右递归
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {// 向左递归
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
4、设计思路（多数）
- 、找到第一个匹配的索引值 mid 的时候，不要马上返回
- 、向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回
- 、向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回
5、代码（多数版）：找到几个返回几个
/**
* 二分查找(多数版)
*
* @param arr 原始数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找的值
* @return
*/
public static List<Integer> binarySearchS(int[] arr, int left, int right, int findVal) {
// 当 left > right 时，说明已经递归完毕，仍没有找到
if (left > right) {
return new ArrayList<Integer>();
}
// 折半取值
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) {
// 右递归
return binarySearchS(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
// 左递归
return binarySearchS(arr, left, mid - 1, findVal);
} else {
// ****************以下代码才是和简单版的区别所在，以上都一样*******
// 1、找到第一个匹配的索引值 mid 的时候，不要马上返回
// 用于接受结果
List<Integer> resIndexList = new ArrayList();
// 2、向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回
int temp = mid - 1;// 左递归起始索引
while (true) {
if (temp < 0 || arr[temp] != findVal) {
break;// 不满足，退出(固二分为有序，左边的第一个不相同，再找也是不同)
} else {
// 加入，左移（再找）
resIndexList.add(temp);
temp -= 1;
}
}
resIndexList.add(mid);
// 3、向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {
break;
} else {
resIndexList.add(temp);
temp += 1;
}
}
return resIndexList;
}
}
6、最终完整代码
/**
* title: 二分查找（单，多数版）
* @author 阿K
* 2020年12月22日 下午9:56:17
*/
public class BinarySearch {
public static void main(String[] args) {
int arr[] = { 1, 8, 10, 89, 1000, 1000, 1234 };
int findVal = 1000;
System.out.println(binarySearch(arr, 0, arr.length - 1, findVal));
System.out.println(binarySearchS(arr, 0, arr.length - 1, findVal));
}
/**
* 二分查找(单数版)
*
* @param arr 原始数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找的值
* @return
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
// 当 left > right 时候，说明已经递归完毕，仍没有找到
if (left > right) {
return -1;
}
// 折半，取值
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) {// 向右递归
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {// 向左递归
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
/**
* 二分查找(多数版)
*
* @param arr 原始数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找的值
* @return
*/
public static List<Integer> binarySearchS(int[] arr, int left, int right, int findVal) {
// 当 left > right 时，说明已经递归完毕，仍没有找到
if (left > right) {
return new ArrayList<Integer>();
}
// 折半取值
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) {
// 右递归
return binarySearchS(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
// 左递归
return binarySearchS(arr, left, mid - 1, findVal);
} else {
// ****************以下代码才是和简单版的区别所在，以上都一样*******
// 1、找到第一个匹配的索引值 mid 的时候，不要马上返回
// 用于接受结果
List<Integer> resIndexList = new ArrayList();
// 2、向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回
int temp = mid - 1;// 左递归起始索引
while (true) {
if (temp < 0 || arr[temp] != findVal) {
break;// 不满足，退出(固二分为有序，左边的第一个不相同，再找也是不同)
} else {
// 加入，左移（再找）
resIndexList.add(temp);
temp -= 1;
}
}
resIndexList.add(mid);
// 3、向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {
break;
} else {
resIndexList.add(temp);
temp += 1;
}
}
return resIndexList;
}
}
}
网友评论