?????????二分查找也稱 半查找（Binary Search），它時一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字 有序 排列。

?注意：使用二分查找的前提是 該數(shù)組是有序的。

在實際開發(fā)中，如果對應(yīng)的索引不存在，我們一般都是返回一個負數(shù)，而且經(jīng)常用? ?- 1? ?來表示。

?

請對一個有序數(shù)組進行二分查找? { 1，8，10，89，1000，1234}，輸入一個數(shù)看看該數(shù)組是否存在此數(shù)，并且求出下標，如果沒有就提示 “沒有這個數(shù)” 。

課后思考題：{1，8，10，89，1000，1000，1234} 當一個有序數(shù)組中，有多個相同的數(shù)組時，如何將所有的數(shù)值都查找到，比如這里面的1000。

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

二分查找的思路分析

1、首先確定該數(shù)組的中間的下標

mid = （left + right ）/? 2

2、然后讓需要查找的數(shù) findVal 和 arr[mid] 比較

? ? ? ? 2.1、findVal > arr[mid] ，說明你要查找的數(shù)在 mid 的右邊，因此需要 遞歸 的向右查找

? ? ? ? 2.1、findVal < arr[mid] ，說明你要查找的數(shù)在 mid 的左邊，因此需要 遞歸 的向左查找

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

//什么時候我們需要結(jié)束遞歸。

1）找到就結(jié)束遞歸

2）遞歸完整個數(shù)組，仍然沒有找到findVal，也需要結(jié)束遞歸? 當left >right 就需要退出

• ?請對一個有序數(shù)組進行二分查找? { 1，8，10，89，1000，1234}，輸入一個數(shù)看看該數(shù)組是否存在此數(shù)，并且求出下標，如果沒有就提示 “沒有? ?這個數(shù)” 。

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   數(shù)組* @param left   左邊的索引* @param right   右邊的索引* @param findVal  要查找的值* @return 如果找到就返回下標，如果沒有找到，就返回-1*/public static int binarySearch(int[] arr, int left, int right, int findVal) {//當left > right 時，說明遞歸整個數(shù)組，但是沒有找到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}當一個有序數(shù)組中，有多個相同的數(shù)值時，如何將所有的數(shù)值都查找到，比如這里的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     數(shù)組* @param left    左邊的索引* @param right   右邊的索引* @param findVal 要查找的值* @return 如果找到就返回下標，如果沒有找到，就返回-1*/public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {//當left > right 時，說明遞歸整個數(shù)組，但是沒有找到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 + ",對應(yīng)的位置為：" + 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;}}}
}