/**
* @Classname BinarySearch
* @Description 二分查找(前提:数组有序)
* @Date 2021/2/26 23:00
* @Created by 12345678
*/
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 1, 1, 4, 6, 8, 9};
int[] arr1 = {1, 3, 5, 6};
ArrayList<Integer> list = binarySerach(arr, 0, arr.length - 1, 1);
binarySerach(arr1, 0, arr1.length - 1, 1);
if (list.size() == 0) System.out.println("-1");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
public static ArrayList<Integer> binarySerach(int[] arr, int left, int right, int findVal) {
if (left > right) {
//通过判断是否为空决定是否找到
return new ArrayList<>();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) {
return binarySerach(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySerach(arr, left, mid - 1, findVal);
} else {
//找到了则向前 向后查找是否存在相同的值 全部加入list中
ArrayList<Integer> indexList = new ArrayList<>();
int temp = mid - 1;
//向左找
while (true) {
if (temp < 0 || arr[temp] != findVal) {
break;
}
indexList.add(temp);
//注意:temp左移
temp -= 1;
}
indexList.add(mid);
//向右找
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {
break;
}
indexList.add(temp);
temp += 1;
}
return indexList;
}
}
}