黑马程序员技术交流社区

标题: 折半查找法 [打印本页]

---

作者: 刘伯阳    时间: 2012-5-31 23:28
标题: 折半查找法
对于这个算法不是很理解，帮我用java代码实现一下。最好代码详细一点，谢谢了~

---

作者: 黄捷    时间: 2012-5-31 23:31
折半查找是对于一组有序排列的数字进行的查找。其思想是取该组数中间位置的数（设每个中间的数位a）与目标数（设目标数为b）进行比较，如果目标数b大于中间位置数a，则取b与a前面数比较，同时运用上述方法，与a前面数取中间为数a1进行比较，如此这样缩小范围，若b小于a，与上同理。直到确定该目标数为止。
附上代码：

public  class HalfSearch
{
public static void main (String[] args)
{
int[] arr=new int[]{2,3,5,6,34,5656};
int a=HalfSearch_2(arr,6);
System.out.println(a);
}
private static int GetIndex(int[] arr,int key)//此方法为普通查找，取目标数一一与该数组里的数进行比较，直到第一次找到该数即停止，输出位置
{
for(int a=0;a<arr.length;a++)
{
if(arr[a]==key)
{
return a;
}
}
return -1;
}
private static int HalfSearch(int[] arr,int key)
{
int min,max,mid;
min=0;
max=arr.length-1;//max不能等于数组长度，否则下标越界
mid=(min+max)/2;
while(key!=arr[mid])
{
if(key>arr[mid])
{
min=mid+1;//若该数大于中间数，则取中间数后一位数为最小数，原数组最大数为最大数，再进行比较
}else if(key<arr[mid])//若该数小于中间数，则取中间数前一位数为最大数，原数组最小数为最小数，再进行比较
{
max=mid-1;
}if(mid>max)//若mid>max则该数不存在于此数组中
{
return -1;
}
mid=(max+min)/2;
}
return mid;
}
private static int HalfSearch_2(int[] arr,int key)
{
int min,mid,max;
min=0;
max=arr.length-1;
mid=(min+max)/2;
while(min<=max)
{
mid=(min+max)/2;
if(key>arr[mid])
{
min=mid+1;
}else if(key<arr[mid])
{
max=mid-1;
}
else
{
return mid;
}
}
return -1;
}
}

---

作者: 余银桂    时间: 2012-6-1 00:40
就是定义俩指针，最好还是理解记忆吧！

---

作者: 王章亚    时间: 2012-6-1 08:10


没有这么复杂其实很好理解。
思想：想要折半查找必须保证你要查找的数组是有序的。
然后定义三个变量（变量名随便你最好有意义）

public static int helfSearch(int[]num,int key){
                int left=0;//数组左边
                int right=num.length-1;//数组右边
                int mid=(left+right)/2;//中间值
                while(key!=num[mid]){
                        if(key>num[mid]){
                                min+=1;
                        }
                        else if(key<num[left]){
                                right-=1;
                        }
                        mid=([left+ right)/2;
                }
               
                return mid;
        }

---

作者: 黑马—陈磊    时间: 2012-6-1 08:24
对于已经排好序了的线性表采用二分查找效率要高些，以下是该算法的一个模子，我是用while实现的，当然可以用递归实现，查找的内容当然也可以不限，如果是一个对象数组，当然就可以去实现对象的查找了，如find(Object[] objs, Object)

import java.util.Arrays;

import java.util.Collections;

public class TestBinarySearch {
    /**
     * 基于升序方式二分法查找
     *
     * @param arr
     *            数组字典
     * @param key
     *            待查的字
     * @return 待查字的数组下标
     */
    public static int find(int[] arr, int key) {
        int len = arr.length;
        int index = 0;// 像一个“偏爱于中间地段”生存的游标，
        int start = 0;
        int end = len - 1;
        while (true) {
            if (start > end) {
                // 返回方式一
                return -1;
                // 如果是按方式一返回说明未找到
            }else{
                index = (start + end) / 2;
                if (key > arr[index]) {
                    start = index+1;
                } else if (key < arr[index]) {
                    end = index-1;
                } else {
                    // 返回方式二
                    return index;
                    // 如果是按方式一返回说明找到了，并且返回查找到的下标
                }
            }
        }//end of while loop
    }

    public static void main(String[] args) {
        int arr[] = { 9,1, 2, 3, 4, 5, 6 };
        // 按照升序方式的排序操作
        Arrays.sort(arr);
        int myIndex = find(arr, 2);
        System.out.println(myIndex);//print result:1
        int myIndex2 = find(arr, 9);
        System.out.println(myIndex2);//print result:6  因为9经过排序后放到了最后去了
        byte y=45;
        //Collections.reverseOrder()颠倒排序方式，如果是int,byte那些是不行的，
        //如果是Object则 可以通过实现Comparable接口
//        Object array[]=null;
//        Arrays.sort(array,   Collections.reverseOrder());
    }
}

---

作者: 黑马—陈磊    时间: 2012-6-1 08:24
对于已经排好序了的线性表采用二分查找效率要高些，以下是该算法的一个模子，我是用while实现的，当然可以用递归实现，查找的内容当然也可以不限，如果是一个对象数组，当然就可以去实现对象的查找了，如find(Object[] objs, Object)

import java.util.Arrays;

import java.util.Collections;

public class TestBinarySearch {
    /**
     * 基于升序方式二分法查找
     *
     * @param arr
     *            数组字典
     * @param key
     *            待查的字
     * @return 待查字的数组下标
     */
    public static int find(int[] arr, int key) {
        int len = arr.length;
        int index = 0;// 像一个“偏爱于中间地段”生存的游标，
        int start = 0;
        int end = len - 1;
        while (true) {
            if (start > end) {
                // 返回方式一
                return -1;
                // 如果是按方式一返回说明未找到
            }else{
                index = (start + end) / 2;
                if (key > arr[index]) {
                    start = index+1;
                } else if (key < arr[index]) {
                    end = index-1;
                } else {
                    // 返回方式二
                    return index;
                    // 如果是按方式一返回说明找到了，并且返回查找到的下标
                }
            }
        }//end of while loop
    }

    public static void main(String[] args) {
        int arr[] = { 9,1, 2, 3, 4, 5, 6 };
        // 按照升序方式的排序操作
        Arrays.sort(arr);
        int myIndex = find(arr, 2);
        System.out.println(myIndex);//print result:1
        int myIndex2 = find(arr, 9);
        System.out.println(myIndex2);//print result:6  因为9经过排序后放到了最后去了
        byte y=45;
        //Collections.reverseOrder()颠倒排序方式，如果是int,byte那些是不行的，
        //如果是Object则 可以通过实现Comparable接口
//        Object array[]=null;
//        Arrays.sort(array,   Collections.reverseOrder());
    }
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2