二分查找也称 半查找（Binary Search），它时一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字 有序 排列。

 注意：使用二分查找的前提是 该数组是有序的。

在实际开发中，如果对应的索引不存在，我们一般都是返回一个负数，而且经常用   - 1   来表示。

请对一个有序数组进行二分查找  { 1，8，10，89，1000，1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示 “没有这个数” 。

课后思考题：{1，8，10，89，1000，1000，1234} 当一个有序数组中，有多个相同的数组时，如何将所有的数值都查找到，比如这里面的1000。

{ 1，8，10，89，1000，1234 } 

二分查找的思路分析

1、首先确定该数组的中间的下标

mid = （left + right ）/  2

2、然后让需要查找的数 findVal 和 arr[mid] 比较

        2.1、findVal > arr[mid] ，说明你要查找的数在 mid 的右边，因此需要 递归 的向右查找

        2.1、findVal < arr[mid] ，说明你要查找的数在 mid 的左边，因此需要 递归 的向左查找

        2.3、findVal < arr[mid]，说明找到，就返回

//什么时候我们需要结束递归。

1）找到就结束递归

2）递归完整个数组，仍然没有找到findVal，也需要结束递归  当left >right 就需要退出

•  请对一个有序数组进行二分查找  { 1，8，10，89，1000，1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示 “没有   这个数” 。

public class BinarySearch {public static void main(String[] args) {int arr[] = {1, 8, 10, 89, 1000, 1234};int resIndex = binarySearch(arr, 0, arr.length - 1, 88);System.out.println(resIndex);}/*** @param arr   数组* @param left   左边的索引* @param right   右边的索引* @param findVal  要查找的值* @return 如果找到就返回下标，如果没有找到，就返回-1*/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;}}
}

• 完成一个课后思考题：{1，8，10，1000，1000，1234}当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的1000

思路分析

1、在找到 mid 索引值，不要马上返回

2、向mid索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList

3、向mid索引值的右边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList

4、将ArrayList返回

public class BinarySearch1 {public static void main(String[] args) {int arr[] = {1, 8, 10, 89, 1000, 1000, 1000, 1000,1234};List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);System.out.println(resIndexList);}/*** @param arr     数组* @param left    左边的索引* @param right   右边的索引* @param findVal 要查找的值* @return 如果找到就返回下标，如果没有找到，就返回-1*/public static ArrayList<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 {ArrayList<Integer> resIndexlist = new ArrayList<Integer>();//向mid索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayListint temp = mid - 1;while (true) {if (temp < 0 || arr[temp] != findVal) { //退出break;}//否则，就temp放入到resIndexlistresIndexlist.add(temp);temp -= 1; //temp 左移}resIndexlist.add(mid);//向mid索引值的右边扫描，将所有满足1000，的元素的下标，加入到集合ArrayListtemp = mid + 1;while (true) {if (temp > arr.length || arr[temp] != findVal) { //退出break;}//否则，就temp放入到resIndexlistresIndexlist.add(temp);temp += 1; //temp右移}return resIndexlist;}}
}

public class BinarySearch2 {public static void main(String[] args) {int[] array = new int[]{10, 11, 12, 13, 14, 15, 16, 17};int target = 10;int index = search(array, target);System.out.println(index);}public static int search(int[] array, int target) {int min = 0;int max = array.length - 1;while (min <= max) {int mid = (min + max) / 2;if (array[mid] == target) {return mid;}if (array[mid] < target) {min = mid + 1;}if (array[mid] > target) {max = mid - 1;}}return -1;}
}

public class BinarySearch3 {public static void main(String[] args) {int[] arr2 = new int[]{-98, -34, 2, 34, 54, 66, 79, 105, 210, 333};int dest1 = 35;int head = 0;  //初始的首索引int end = arr2.length - 1;  //初始的末索引boolean isFlag1 = true;while (head <= end) {int middle = (head + end) / 2;if (dest1 == arr2[middle]) {System.out.println("找到了指定的元素，位置为：" + middle);isFlag1 = false;break;} else if (arr2[middle] > dest1) {end = middle - 1;} else {head = middle + 1;}}if (isFlag1) {System.out.println("很遗憾，没有找到的啦！");}}
}

public class BinarySearch4 {public static void main(String[] args) {int[] arr2 = new int[]{2, 4, 5, 8, 12, 15, 19, 26, 37, 49, 51, 66, 89, 100};int target = 17;int head = 0;  //默认的首索引int end = arr2.length - 1; //默认的尾索引boolean isFlag = false;while (head <= end) {int middle = (head + end) / 2;if (target == arr2[middle]) {System.out.println("找到了" + target + ",对应的位置为：" + middle);isFlag = true;break;} else if (target > arr2[middle]) {head = middle + 1;} else {end = middle - 1;}}if (!isFlag) {System.out.println("不好意思，未找到");}}
}

public class BinarySearch5 {public static void main(String[] args) {int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};System.out.println(binarySearch(arr, 150));}public static int binarySearch(int[] arr, int number) {int min = 0;int max = arr.length - 1;while (true) {if (min > max) {return -1;}int mid = (min + max) / 2;if (arr[mid] > number) {max = mid - 1;} else if (arr[mid] < number) {min = mid + 1;} else {return mid;}}}
}