精华内容
下载资源
问答
  • 数组二分查找

    2019-05-23 19:01:03
    数组二分查找(根据元素) 代码详解 package arrays; /** 数组二分查找 条件:数组元素不能重复且有序 结果:有则返回下标元素 无则返回-1 */ public class ArrayBinarySearch { ...

    数组二分查找(根据元素)

    代码详解

    package arrays;
    /**
    
    		数组二分查找
     				条件:数组元素不能重复且有序
     				结果:有则返回下标元素
     						 无则返回-1
     				
    
     */
    public class ArrayBinarySearch {
    	public static void main(String[] args) {
    		//初始化一个有序无重复的数组为目标查询数组
    		int[] arr=new int[]{0,1,2,3,4,5,6,7,8,9};
    		//查找目标元素
    		int a=10;
    		//查找的结果
    		int index=-1;
    		//数组开始下标
    		int head=0;
    		//数组结束小标
    		int end=arr.length-1;
    		//数组中间下标
    		int binary=(end+head)/2;
    		//while循环遍历数组二分查找
    		while(true){
    			//查询的元素不在数组范围内,则直接退出循环
    			if(a<arr[head]  || a>arr[end]){
    				break;
    			}
    			
    			//判断中间下标的元素是否与查找元素相同
    			if(arr[binary]==a){
    				//相同,则直接将下标赋值给结果index
    				index=binary;
    				//找到结果退出循环
    				break;
    				//中间下标的元素与查找元素不相同
    			}else{
    				//再次判断,中间下标元素的值是否大于查找的元素,如果大于,则重新赋值数组结束下标,查找前半段
    				if(arr[binary]>a){
    					//重新赋值数组结束下标
    					end=binary-1;
    					//中间下标元素的值小于查找的元素,则重新赋值数组开始下标,查找后半段
    				}else{
    					//重新赋值数组开始下标
    					head=binary+1;
    				}	
    				//数组中间下标重新赋值
    				binary=(end+head)/2;
    			}
    		}
    		//查询结果输出
    		System.out.println("数组二分查找,元素"+a+"的下标:"+index);
    		
    	}
    }
    
    

    数组二分查找方法简易封装

    package arrays;
    /**
     * 数组二分查找方法简易封装
     * @author Administrator
     *
     */
    public class BinarySearch {
    	public int binarySearch(int a,int[] arr){
    		
    		//查找的结果
    				int index=-1;
    				//数组开始下标
    				int head=0;
    				//数组结束小标
    				int end=arr.length-1;
    				//数组中间下标
    				int binary=(end+head)/2;
    				//while循环遍历数组二分查找
    				while(true){
    					//查询的元素不在数组范围内,则直接退出循环
    					if(a<arr[head]  || a>arr[end]){
    						break;
    					}
    					
    					//判断中间下标的元素是否与查找元素相同
    					if(arr[binary]==a){
    						//相同,则直接将下标赋值给结果index
    						index=binary;
    						//找到结果退出循环
    						break;
    						//中间下标的元素与查找元素不相同
    					}else{
    						//再次判断,中间下标元素的值是否大于查找的元素,如果大于,则重新赋值数组结束下标,查找前半段
    						if(arr[binary]>a){
    							//重新赋值数组结束下标
    							end=binary-1;
    							//中间下标元素的值小于查找的元素,则重新赋值数组开始下标,查找后半段
    						}else{
    							//重新赋值数组开始下标
    							head=binary+1;
    						}	
    						//数组中间下标重新赋值
    						binary=(end+head)/2;
    					}
    				}
    				
    				return index;
    		
    	}
    }
    
    
    展开全文
  • JAVA数组二分查找

    2019-02-27 22:16:01
    JAVA数组二分查找前言查找原理代码实现 前言 二分查找是一种比较高效的查找方式,使用此查找方式需要先将数组进行排序,如果数组未经排序效率就会很低,所以数组是必须要经过排序的。 查找原理 Created with Raphaë...

    JAVA数组二分查找

    前言

    二分查找是一种比较高效的查找方式,使用此查找方式需要先将数组进行排序,如果数组未经排序效率就会很低,所以数组是必须要经过排序的

    查找原理

    Created with Raphaël 2.2.0 排序后数组 计算数组中间值 判断数组中间值是否 等于我们要查找的元素 是我们查找的元素返回当前middle下标 结束 判断当前中间下标是否已经为0 返回-1代表未找到此元素 判断当前中间元素是否 大于我们要查找的元素 如果不大于那说明我们 要找的元素在中间值 的右边(数组从小到大排序), 那么递归将之前的数组的start 换为中间值。 如果不大于那说明我们 要找的元素在中间值 的左边(数组从小到大排序), 那么递归将之前的数组的end 换为中间值。 yes no yes no yes no

    代码实现

    @Test
        public void test1() {
            Integer[] arr = new Integer[]{4, 3, 2, 1, 5, 10, 1, 11, 1, 1, 2, 123, 42142, 1};
            arr = mergeSort(arr, Comparator.naturalOrder()); //使用二分法需要先将数组排序 (归并排序)
    
            for (Integer integer : arr) {
                System.out.println(integer);
            }
    
            System.out.println(binarySearch(arr, 42142, 0, arr.length, Comparator.naturalOrder()));
        }
    
        /**
         * 使用二分法查找元素,如果有多个仅仅只返回其中一个数组下标(乱序)。
         *
         * @param arr 目标数组
         * @param find 查找元素
         * @param start 数组开始下标
         * @param end 数组结束下标
         * @param comparator 元素比较规则
         * @return 查找的元素在目标数组的下标
         */
        private int binarySearch(Object[] arr, Object find, int start, int end, Comparator comparator) {
            if (arr == null) throw new NullPointerException("arr can not be empty!");
    
            int middle = (end - start) / 2 + start;
    
            int result = comparator.compare(arr[middle],find);
    
            if(middle == 0 && result != 0) return -1;
    
            if(result > 0) {
                return binarySearch(arr, find, start, middle, comparator);
            } else if(result < 0) {
                return binarySearch(arr, find, middle, end, comparator);
            } else {
                return middle;
            }
        }
    
        /**
         * 归并排序
         *
         * @param arr 排序数组
         * @param comparator 比较规则
         * @return 排序后的数组
         */
        private <T> T[] mergeSort(T[] arr, Comparator<T> comparator) {
            T[] cache = arr.clone();
            int step = 2;
    
            while (step <= arr.length * 2) {
                int c = 0;
                for (int i = 0; i < arr.length; i += step) {
                    int l = i, r = l + (step >> 1) > arr.length ? arr.length : i + (step >> 1);
                    int lm = r;
                    int rm = i + step > arr.length ? arr.length : i + step;
    
                    while (l < lm && r < rm) {
                        if (comparator.compare(arr[l],arr[r]) > 0) {
                            cache[c] = arr[r];
                            r++;
                            c++;
                        } else {
                            cache[c] = arr[l];
                            l++;
                            c++;
                        }
                    }
                    while (l < lm) {
                        cache[c] = arr[l];
                        l++;
                        c++;
                    }
                    while (r < rm) {
                        cache[c] = arr[r];
                        r++;
                        c++;
                    }
                    System.arraycopy(cache, 0, arr, 0, cache.length);
                }
                step = step << 1;
            }
    
            return (T[]) cache;
        }
    

    归并排序可以参考 > 归并排序

    展开全文
  • java数组二分查找

    2015-11-02 16:56:58
    Java数组二分查找代码,将给定数组排序,然后接收键盘键入的整形数字,并查找该数字。
  • 算法描述,一个有序的数组,从开始到中间截取一段数组放到数组的尾部,这个数组会变成循环有序的数组,在这个循环有序的数组中进行二分查找 例如 1,2,3,4,5,6,7,8,9 截取前4位放到尾部会变成5,6,7,8,9...


    算法描述,一个有序的数组,从开始到中间截取一段数组放到数组的尾部,这个数组会变成循环有序的数组,在这个循环有序的数组中进行二分查找

    例如   1,2,3,4,5,6,7,8,9    截取前4位放到尾部会变成5,6,7,8,9,1,2,3,4 变成循环有序的数组

    算法实现:采用二分查找的方式,获取中间的一个数组,然后看一下转折点在中间数的左边还是右边,然后进行分情况讨论

    具体实现代码如下:

    public static void main(String[] args) {
        int[] array = new int[10];
        array[0] = 8;
        array[1] = 9;
        array[2] = 10;
        array[3] = 11;
        array[4] = 12;
        array[5] = 13;
        array[6] = 3;
        array[7] = 4;
        array[8] = 5;
        array[9] = 6;
        System.out.println("**************");
        System.out.println(find(array, 10, 4));
    }

    /**
     * 循环有序的数组进行二分查找
     * @param A
     */
    public static int find(int[] A, int n, int target){
        if(n<=0)
            return -1;
        int left = 0, right = n-1;
        while(left<=right)
        {
            int mid = left + ((right-left)/2);
            if(A[mid] == target){
                return mid;
            }
            //转折点在右半边
            if(A[left] <= A[mid])
            {
                if(A[left] <= target && target < A[mid]){
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            else //转折点在左半边
            {
                if(A[mid] < target && target <= A[right]){
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
     

    展开全文
  • 数组二分查找

    2020-04-27 17:30:01
    数组二分查找法 1.二分查找法思想 二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],...

    数组二分查找法

    1.二分查找法思想

    二分查找法使用的前提是有序排列的数组。
    二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

    2.二分查找法示例

    public class MindArray {
        public static void main(String[] args) {
            boolean b = mindArray(31);
            System.out.println("b = " + b);
        }
    
        public static boolean mindArray(int findArrayValue) {
            //定义有序的一维数组
            int[] arr = {1, 3, 5, 7, 9, 10, 12, 15, 18, 20};
    
            boolean isFlag = false;
            //1.数组开头索引
            int head = 0;
            //2.数组末尾索引
            int end = arr.length - 1;
    
            while (head <= end) {
                //3.数组中间索引
                int mind = (head + end) / 2;
                //4.查找的值是否等于中间值
                if (findArrayValue == arr[mind]) {
                    System.out.println("arr{\n[查找的元素在数组中索引的位置:" + 
                    mind +"]\n" + "[查找到的数组元素值:"+arr[mind]+"]\n}");
                    isFlag = true;
                    break;
                    //5.中间值大于查找的值,将数组末尾索引移到中间索引减1的位置
                } else if (findArrayValue < arr[mind]) {
                    end = mind - 1;
                    //6.中间值小于查找的值,将数组开头索引移到中间索引加1的位置
                } else {
                    head = mind + 1;
                }
            }
            if (!isFlag) {
                System.out.println("没有找到查找的元素");
            }
            return isFlag;
        }
    }
    
    展开全文
  • 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 又例如{...
  • java-数组二分查找

    千次阅读 2018-08-13 21:17:37
    * 数组高级二分查找代码 * B:注意事项 * 如果数组无序,就不能使用二分查找。 * 因为如果你排序了,但是你排序的时候已经改变了我最原始的元素索引。 */ public static void main(Strin...
  • java代码-数组二分查找
  • php教程二维数组二分查找需找数组中某一元素下标 成功不是将来才有的而是从决定去做的那一刻起持续累积而成以下的在PHP中二维数组二分查找需找数组中某一元素下标希望对大家有所帮助更多信息请关注 如果你的数组有...
  • 无序(未排序)数组二分查找

    千次阅读 2018-04-08 18:28:39
    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。但是对于无序数组,我们可以先排序在二分,但还有一种技巧...
  • 主要介绍了C++实现旋转数组二分查找方法,涉及数组的操作,有值得借鉴的技巧,需要的朋友可以参考下
  • 带有重复元素的有序数组二分查找

    千次阅读 2016-12-07 16:52:53
    其实这道题也很容易想到二分查找,时间复杂度为o(logn),但是二分查找需要注意一个细节,就是当遇到重复元素时,让mid指针跳过所有重复元素,这也是很多粗心的小伙伴非常容易忽略的,也 是很多面试官喜
  • java数组二分查找

    2018-02-02 20:15:42
    语言:java  ...//二分查找法 / 折半查找法 class BinarySeacheDemo { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int index = binarySearc...
  • Java基础篇---------数组二分查找

    千次阅读 2018-08-31 19:55:46
    首先需要了解的是二分查找法是干什么用的。 假设有
  • Java中数组二分查找

    2019-10-30 18:56:16
    但是二分查找有一个前提就是数组必须有序。 二分查找的思想 首先假设数组元素呈升序排列,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止;如果x<a[n/2],则我们...
  • 原理:在使用二分查找算法之前先要确定被查找的数组必须有序的,即确定待寻找的元素的范围是[low, high],然后逐步缩小范围直到找到或找不到该元素为止。具体做法是:先取数组中间位置(mid=(low+high)/2)的数据...
  • 主要介绍了JavaScript使用二分查找算法在数组中查找数据的方法,较为详细的分析了二分查找法的原理与javascript实现技巧,需要的朋友可以参考下
  • 《C语言入门》简单有序数组二分查找代码实现

    多人点赞 热门讨论 2021-11-14 11:25:01
    想必学过编程的朋友或多或少都听说过二分查找,本文将给C语言入门的朋友具体介绍一下二分查找的原理和代码实现。 1.简单原理 在一个有序数组中(如图),若想查找一个具体数值,多数人可能会想到历遍数组的方法,...
  • 循环递增的数组 二分查找

    千次阅读 2014-12-30 11:17:19
    44. 对已排好序的数组 A,一般来说可用二分查找 可以很快找到。现有一特殊数组 A[],它是循环递增的,如 A[]={ 17 19 20 25 1 4 7 9},试在这样的数组中找一元素 x ,看看是否存在。 请写出你的算法,必要时可写伪...
  • 算法13--旋转数组二分查找

    千次阅读 2018-11-03 12:02:20
    数组基本有序可以考虑二分查找来解决,考虑旋转数组的特点前半部分递增后半部分递减,使用两个指针,第一个index1指向递增部分,第二个index2指向递减部分,不断逼近,当两者距离之差index2-index1等于1,可以得到...
  • 二维数组中的二分查找

    千次阅读 2018-08-08 18:03:48
    题目来源:剑指offer 题目描述 在一个二维数组中(每个一维数组的...由于二维数组每一行都是有序递增,因此可以将二维数组拆分成每一行来看,对每一行用二分查找进行遍历,从而得出答案。   代码 public clas...
  • 主要介绍了C语言数组中的查找的实例的相关资料,需要的朋友可以参考下
  • 采用递归分治法,类似于二分查找,找左边最大值和右边最大值,然后比较,返回比较大的那一个。递归的出口是当左下标>=右下标时,返回当前元素。 例:if(i>=j) return a[i]; 不多说了,思路比较简单,直接堆...
  • (旋转数组的)二分查找算法

    千次阅读 2019-06-17 13:32:21
    二分查找算法(Binary Search)是一种高效的、应用广泛的查找算法。它是一种采用分治策略的算法。 基本二分查找算法 二分查找是针对顺序存储的有序序列的;二分查找的基本思想是:将目标元素与序列中位数比较,如果...
  • 有序序列二分查找算法基本思想: 例子 有序数组:{1,5,8,9,12,17,23,25,29,34,36,37,40,42,45} 数组下标:{0,1,2,3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14} 查找数5 1.在一个查询区间...
  • 问题:请实现以下函数int indexOf(int [] ...解决:首先,使用二分查找找到数组的 “临界点”,临界点满足两个情况: array[left] < array[mid] array[left] <= array[mid] 只有确定分界点,确定了key的范...
  • 基于数组二分查找算法的实现

    千次阅读 2015-04-26 09:39:51
    基于数组二分查找算法的实现 二分查找 查找 算法 赵振江 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 288,349
精华内容 115,339
关键字:

数组二分查找