二分查找
文章目录
二分查找算法
- 对一个有序数组的查找
准备
- 使用冒泡排序算法对数组排序
12345678910111213 | //冒泡排序 , 从小到大public void bubbleSort(Integer[] array){ //外层遍历n-1次 for (int i = 0; i < array.length-1; i++) { for(int j=array.length-1;j>i;j--){ if (array[j]<array[j-1]) { Integer t=array[j]; array[j]=array[j-1]; array[j-1]=t; } } }} |
|---|
非递归实现
- 传入的数组是一个从小到大的数组
123456789101112131415161718192021222324252627 | /** * 二分查找算法 * @param array 数组，必须是从小到大有序的 * @param key 查找的关键字 * @return 如果成功查找到，那么返回索引，否则返回-1 */ public Integer binarySearch(Integer[] array,Integer key){ int low=0; //最前面的索引默认是0 int high=array.length-1; //最后面的索引默认为最后一个 //从小到大的数组，low>high判断数组中是否有元素 if (key<array[low]||key>array[high]||low>high) { return -1; } while(low<=high){ int middle=(low+high)/2; //左右索引的中间值 //如果要查找的数据大于中间值，表示 if (key>array[middle]) { low=middle+1; //那么查找右半部分 }else if (key<array[middle]) { //如果查找的数据小于中间值，那么查找左半部分 high=middle-1; }else { //如果key==middle,那么直接返回middle即可 return middle; } } return -1; //没有找到，返回-1 } |
|---|
递归实现
12345678910111213141516171819202122 | /** * 递归的二分查找 * @param array 从小到大的有序数组 * @param key 需要查找的数 据 * @param low 左边的索引 初始值为0 * @param high 右边的索引 初始值为array.length-1 * @return 查找成功返回索引，否则返回-1 */public Integer recursionBinarySearch(Integer[] array,Integer key,Integer low,Integer high){ //从小到大的数组，low>high判断数组中是否有元素 if (key<array[low]||key>array[high]||low>high) { return -1; } Integer middle=(low+high)/2; //中间索引 if (key>array[middle]) { return recursionBinarySearch(array, key, middle+1, high); }else if(key<array[middle]){ return recursionBinarySearch(array, key, low, middle-1); }else { return middle; }} |
|---|