二分查找的原理：(所查找的数组必须是有序的)
查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；
如果查找元素大于(小于)中间元素，则在数组大于(小于)中间元素的那一半区间中查找，而且跟开始一样从中间元素开始比较。直到在某一步判断时数组为空数组，说明没有找到该元素
二分查找的思路：
先找到有序数组的中间位置mid = (left+right)/2，然后用有序数组找到中间位置的元素，即arr[mid]与目标元素findVal进行比较，若arr[mid]大于findVal，即说明目标元素findVal在arr[mid]的左边，我们就将索引right左移为(mid-1)，若arr[mid]小于findVal，即说明目标元素findVal在arr[mid]的右边，我们就将索引left右移为(mid+1)，不断的如此折半查找，直到满足条件findVal==arr[mid]为止，说明查找到此元素的索引mid。
代码实现：
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; } }
经过测试后，可知上诉述的二分查找只能找到目标元素的一个索引，若目标元素在数组有多个，则不能将所有的目标索引找出来。由此我们可以继续对这个二分查找进行完善。
完善思路：
将binarySearch()方法的返回值改为List集合，在else语句中进行对第一次找到的mid，即第一次找到的findval的索引的左右进行顺序查找，若找到则添加到List集合中。下面是博主的实现代码，可供大家参考。若有更好的实现方式，也请大佬们指教。
public static List<Integer> binarySearch2(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 binarySearch2(arr, mid + 1, right, findVal); } else if (findVal < midVal) { // 向左递归 return binarySearch2(arr, left, mid - 1, findVal); } else { List<Integer> resIndexlist = new ArrayList<Integer>(); // 向 mid 索引值的左边扫描，将所有满足 findVal， 的元素的下标，加入到集合 ArrayList int temp = mid - 1; while (true) { if (temp < 0 || arr[temp] != findVal) {// 退出 break; } // 否则，就 temp 放入到 resIndexlist resIndexlist.add(temp); temp -= 1; // temp 左移 } resIndexlist.add(mid); // // 向 mid 索引值的右边扫描，将所有满足 findVal， 的元素的下标，加入到集合 ArrayList temp = mid + 1; while (true) { if (temp > arr.length - 1 || arr[temp] != findVal) {// 退出 break; } // 否则，就 temp 放入到 resIndexlist resIndexlist.add(temp); temp += 1; // temp 右移 } return resIndexlist; } }
