[算法] 二分查找

package com.guigu.search;import java.util.ArrayList;
import java.util.Arrays;/*** @author: guorui fu* @versiion: 1.0* 二分查找 直接适用于已经排序完成的数组*/
public class BinarySearch {public static void main(String[] args) {int arr[] = {1,8,8,89,101,1234};ArrayList<Integer> resIndex = binarySearch(arr, 0, arr.length, 8);if (resIndex.isEmpty()){System.out.println("找不到目标值");}else{System.out.println("所找值下标=" + resIndex);}}//二分查找算法/**** @param arr 数组* @param left 左边的索引* @param right 右边的索引* @param findVal 要查找的值* @return 返回下标 或返回-1*/public static ArrayList<Integer> binarySearch(int[] arr,int left,int right,int findVal){//如果left > right 则说明找不到 返回-1if (left > right){return new ArrayList<Integer>();}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 {//找到mid索引值，不要马上返回 加入集合 继续扫描ArrayList<Integer> resIndexList = new ArrayList<>();int temp = mid -1;while (true){if (temp < 0 || arr[temp] != findVal){//退出break;}//否则，就temp放入到集合中resIndexList.add(temp);temp -= 1;//temp左移}resIndexList.add(mid);//向mid索引值的右边扫描，将所有满足1000 的元素的下标，加入到集合ArrayListtemp = mid + 1;while (true){if (temp > arr.length - 1 || arr[temp] != findVal){//退出break;}//否则，就temp放入到集合中resIndexList.add(temp);temp += 1;//temp右移}return resIndexList;}}
}