Java 二分法搜索数组

2014-06-25· 4297 次浏览
## 介绍 二分法充分利用了元素间的次序关系。 ### 基本思想 将n个元素(假设元素呈升序排列)分成个数大致相同的两半,取a\[n/2\]与欲查找的x作比较。 如果x=a\[n/2\],则找到x,算法终止。 如果x<a\[n/2\],则只要在数组a的左半部继续搜索x。 如果x>a\[n/2\],则只要在数组a的右半部继续搜索x。 ### 局限性 必须是在有序的元素中进行的,不能在无序的元素中使用。 ## 示例 ### 递归方式搜索 ```java import java.util.Arrays; public class BinarySearchTest { public static int binarySearch(int[] array, int number, int startIndex, int endIndex) { int middleIndex = (startIndex + endIndex) / 2; // 判断要搜索的数字是否合理 if (startIndex > endIndex) return -1; if (number < array[middleIndex]) { // 搜索数字位于数组前半部分 return binarySearch(array, number, startIndex, middleIndex - 1);// 运用递归 } else if (number > array[middleIndex]) { // 搜索数字位于数组后半部分 return binarySearch(array, number, middleIndex + 1, endIndex);// 运用递归 } else if (number == array[middleIndex]) { return middleIndex; } return -1; } public static void main(String[] args) { int[] array = new int[] { 12, 3, 2, 18, 24, 15, 20 }; // 二分法搜索元素之前必须对数组进行排序 Arrays.sort(array); // 要查找的值 int number = 18; System.out.println("排序后的数组:" + Arrays.toString(array)); System.out.println("元素 " + number + " 所在的位置下标是:" + binarySearch(array, number, 0, array.length - 1)); number = 1; System.out.println("元素 " + number + " 所在的位置下标是:" + binarySearch(array, number, 0, array.length - 1)); } } ``` ### 遍历方式搜索 ```java import java.util.Arrays; public class BinarySearchTest { public static int binarySearch(int[] array, int number) { int beginIndex = 0; int endIndex = array.length - 1; // 循环判断,根据起始位置与结束位置是否相等 while (beginIndex <= endIndex) { // 获得数组中间位置 int midIndex = (beginIndex + endIndex) / 2; if (number < array[midIndex]) { // 搜索数字位于数组前半部分 // 重新定位结束位置 endIndex = midIndex - 1; } else if (number > array[midIndex]) {// 搜索数字位于数组后半部分 // 重新定位起始位置 beginIndex = midIndex + 1; } else {// 搜索数字位于数组中间 return midIndex; } } return -1; } public static void main(String[] args) { int[] array = new int[] { 12, 3, 2, 18, 24, 15, 20 }; // 二分法搜索元素之前必须对数组进行排序 Arrays.sort(array); // 要查找的值 int number = 18; System.out.println("排序后的数组:" + Arrays.toString(array)); System.out.println("元素 " + number + " 所在的位置下标是:" + binarySearch(array, number)); number = 1; System.out.println("元素 " + number + " 所在的位置下标是:" + binarySearch(array, number)); } } ``` ## 二分法模板 ```java public static int bisectionSearch(int[] arr, int key) {     int start = 0;     int end = arr.length - 1;     while (start <= end) {         int middle = (start + end) / 2;         if (key < arr[middle]) {             end = middle - 1;         } else if (key > arr[middle]) {             start = middle + 1;         } else {             return middle;         }     }     return -1; } ```