- 二分查找(Java)
- 1.概念
- 2.思路分析
- 3.代码
2.思路分析二分查找（Binary Search）也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）
3.代码1.首先确定数组的中间下标：mid=（left+right）/2
2.然后让需要查找的数findVal和arr[mid]比较
2.1 findVal > arr[mid] 说明要查找的数在 mid 右边，因此向右递归查找
2.2 findVal < arr[mid] 说明要查找的数在 mid 左边，因此向左递归查找
2.3 findVal = arr[mid] 说明找到，既返回
3.何时结束递归？
3.1 找到就结束递归
3.2 递归完整个数组仍然没找到findVal，也需要结束递归（left>right就需要结束）
package DataStructuresAlgorithm.Search;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[]{1, 8, 10, 89, 1000, 1234};
int resIndex = binarySearch(arr, 0, arr.length - 1, 88);
System.out.println(resIndex);
}
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个1000，查找后只会返回第一个1000的下标，代码还可以改进
1.找到第一个匹配的索引值 mid 的时候，不要马上返回
2.向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
3.向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
public static ArrayList binarySearchMore(int[] arr, int left, int right, int findVal) {
//当left>right，说明递归了整个数组，没找到
if (left > right) {
return new ArrayList();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
ArrayList resIndexList = new ArrayList<>();
if (findVal > midVal) {//向右递归
return binarySearchMore(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySearchMore(arr, left, mid - 1, findVal);
} else {
//向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
int temp = mid - 1;
while (true) {
if (temp < 0 || findVal != arr[temp]) {
break;
}
//否则，就把temp放到ArrayList中
resIndexList.add(temp);
temp -= 1;//temp左移
}
resIndexList.add(mid);
//向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || findVal != arr[temp]) {
break;
}
//否则，就把temp放到ArrayList中
resIndexList.add(temp);
temp += 1;//temp右移
}
}
return resIndexList;
}
完整代码
package DataStructuresAlgorithm.Search;
import java.util.ArrayList;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = new int[]{1, 8, 10, 89, 1000, 1000, 1000, 1000, 1234};
// int resIndex = binarySearchOne(arr, 0, arr.length - 1, 88);
// System.out.println(resIndex);
ArrayList reIndexList = binarySearchMore(arr, 0, arr.length - 1, 1000);
System.out.println(reIndexList);
}
public static int binarySearchOne(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 binarySearchOne(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySearchOne(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
public static ArrayList binarySearchMore(int[] arr, int left, int right, int findVal) {
//当left>right，说明递归了整个数组，没找到
if (left > right) {
return new ArrayList();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
ArrayList resIndexList = new ArrayList<>();
if (findVal > midVal) {//向右递归
return binarySearchMore(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySearchMore(arr, left, mid - 1, findVal);
} else {
//向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
int temp = mid - 1;
while (true) {
if (temp < 0 || findVal != arr[temp]) {
break;
}
//否则，就把temp放到ArrayList中
resIndexList.add(temp);
temp -= 1;//temp左移
}
resIndexList.add(mid);
//向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || findVal != arr[temp]) {
break;
}
//否则，就把temp放到ArrayList中
resIndexList.add(temp);
temp += 1;//temp右移
}
}
return resIndexList;
}
}
