java基础-数组的折半查找原理

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　作者：尹正杰

版权声明：原创作品，谢绝转载！否则将追究法律责任。

 

 

　　如果让你写一个数组的查找功能，需求如下：在一个数组中，找一个元素，是否存在于数组中， 如果存在就返回这个元素，如果没有这个元素，就可以返回一个负数。今天我们来介绍一下折半查找的原理，并自己用代码实现折半查找。

 

 

一.数组的折半查找原理

　　二分查找发，也叫折半查找，它的前提就是被查找的数组的元素，必须是有序（本篇博客数据案例均为升序）排列的。

1>.在查找前对数组进行折半操作 （初始化指针位置）　　

　　折半公式　=  （最大索引+最小索引）/ 2

 　　首先我们可以利用指针思想，假设有一个指针指向最大值(MAX)，有一个指针指向最小值(MIN)，还有一个指针指向的是最大值和最小值之间的索引(MID)。我把这个过程称为初始化指针位置。

2>.折半后的指针索引和被查找元素比较。

　　若被查找元素的值（12）大于中间索引上的值（10），我们就把最小值指针（MIN）移动到中间指针(MID)索引的下一个索引位置，如下图：

3>.若没有匹配到就继续折半后的指针索引和被查找元素比较。 

 

 　　若被查找元素的值（12）小于中间索引上的值（15），我们就把最大值指针（MAX）移动到中间指针(MID)索引的上一个索引位置，如下图：

 

4>.若没有匹配到就继续折半后的指针索引和被查找元素比较。 

　　若被查找元素的值（12）小于中间索引上的值（13），我们就把最大值指针（MAX）移动到中间指针(MID)索引的上一个索引位置，如下图：

 

5>.若没有匹配到就继续折半后的指针索引和被查找元素比较。 

　　当小指针(MIN)的索引(4)超过了大指针(MAX)的索引(3)时，就需要停止查找了，如果真有这种情况发生，说明没有查到被查找元素的值（12），此时会返回一个负数（-1）,当然如果查找到了就返回其在数组中的索引即可。

二.数组的折半查找代码实现

1 /* 2 @author :yinzhengjie 3 Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/ 4 EMAIL:y1053419035@qq.com 5 */ 6  7 package cn.org.yinzhengjie.demo; 8  9 public class Demo {10 11     public static void main(String[] args) {12         int[] arr = {1,4,7,10,13,15,21,25};13         int index = binarySearch(arr,12);14         System.out.println(index);15         index = binarySearch(arr,7);16         System.out.println(index);17     }18 19     public static int binarySearch(int[] arr,int key) {20         //定义三个指针变量。21         int min = 0;22         int max = arr.length - 1;23         int mid = 0;24         //循环折半，条件， min<=max25         while(min <= max) {26             //公式，计算中间索引27             mid = (min+max)/2;28             //让被找元素和中间索引元素进行比较29             if(key>arr[mid]) {30                 min = mid +1;31             }else if(key 

1 /* 2 @author :yinzhengjie 3 Blog:http://www.cnblogs.com/yinzhengjie/tag/Java%E5%9F%BA%E7%A1%80/ 4 EMAIL:y1053419035@qq.com 5 */ 6  7 package cn.org.yinzhengjie.note; 8  9 /*10  * 二分查找11  * 折半查找12  *     前提:要找的数组必须是有序的.13  *     每次都用中间的元素和要找的元素进行比较14  * 15  */16 public class BinarySearchDemo {17 18     public static void main(String[] args) {19         int[] arr = {1,4,7,10,13,15,21,25};20         int index = binarySearch(arr,21);21         //对返回值进行判断22         if(index == -1){23             System.out.println("no such element");24         }else{25             System.out.println("index is : " + index);26         }27     }28     29     30     //自定义方法,折半查找31     public static int binarySearch(int[] arr,int value){32         int min = 0;33         int max = arr.length - 1;34         int mid = (min + max) / 2;35         while(true){    36             //判断要找的数落在左边还是右边37             if(value > arr[mid]){38                 min = mid + 1;39             }else if(value < arr[mid]){40                 max = mid - 1;41             }else{42                 return mid;43             }44             //重新计算中间的索引值45             mid = (min + max) / 2;46             //没有找到的条件判断47             if(min > max){48                 return -1;49             }50         }51     }52 }53 54 55 /*56 以上代码执行结果如下：57 index is : 658 */