5.2.4查找 顺序查找和折半查找示例程序: public class Search t ∥/顺序查找 public int sequentia lSearch(int arr[l, int key& for (int k= 0; k< arr length; k++) r return k; 成功,返回该数组元素的位置(即索引) return -1 ∥/失败,返回-1 /折半查找 int high= arr length-;∥初始( public int binary Search(int arr[l, int key) nt low =0; while (low < high)t int mid=(ow+high)/2;∥/取折半值 if (arr[mid]== key) return mid ∥/成功,返回该数组元素的位置(即索引) Ise if (arr[mid]< key low mid +1. ∥/定位查找上半段 els high mid-1 ∥/定位查找下半段 return -l; ∥/失败,返回-1Java程序设计大学教程 5.2.4 查找 ◼ 顺序查找就是将要查找的数据的关键字按一定的顺序挨个与列 表中的数据进行比较，相等时就找到了所要的数据。 ◼ 对有序的列表可以使用更有效率的折半查找。折半查找是从一 个列表的中间的元素来测试的，这将能够判别出目标在列表里 的前半部还是后半部分。如果在前半部分，就不需要查找后半 部分。如果在后半部分，就不需要查找前半部分。换句话说， 可以通过判断排除一半的列表。重复这个过程直到找到目标或 是目标不在这个列表里。 顺序查找和折半查找示例程序： public class Search { //顺序查找 public int sequentialSearch(int arr[], int key) { for (int k = 0; k < arr.length; k++) if (arr[k] == key) return k; // 成功,返回该数组元素的位置（即索引） return -1; // 失败,返回-1 } //折半查找 public int binarySearch(int arr[], int key) { int low = 0; // 初始化 int high = arr.length - 1; while (low <= high) { int mid = (low + high) / 2; // 取折半值 if (arr[mid] == key) return mid; // 成功,返回该数组元素的位置（即索引） else if (arr[mid] < key) low = mid + 1; // 定位查找上半段 else high = mid - 1; // 定位查找下半段 } return -1; // 失败,返回-1 } }