`
uule
  • 浏览: 6352670 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

有序数组的二分查找

 
阅读更多

二分查找法是对一组有序的数字中进行查找,传递相应的数据,查找传递的数据对应的数组下标,没有找到返回-1

有序数组二分查找的基本原理:因为数组是有序的,先找到中间位置的值,如果目标比这个值大,那么该目标必定在数组的右半部分,以此循环或者递归,一直找到这个数值为止。此算法的时间复杂度为O(logN),N为数组的长度 (2的X次方 == N,所以复杂度即为 O(logn) )

 

public class SortedArrayBinarySearch {
    
    public static void main(String[] args) {
        int[] source=new int[]{1,3,5,7,9,12}; 
        int key = 12;
        System.out.println(binaryRecurSearch(source, key));;
        System.out.println(binarySearchLoop(source, key));;
    }
    
    public static int binaryRecurSearch(int[] source, int key){
        return binarySearchRecursive(source, key,0,source.length-1);
    }
    

     //递归查找
    private static int binarySearchRecursive(int[] source, int key,int beginIndex,int endIndex){
        int midIndex = (beginIndex+endIndex)/2;
        if(key<source[beginIndex]  ||  key>source[endIndex] || beginIndex>endIndex){  
            return -1;  
        }  
        System.out.println("=======");
        if(key == source[midIndex]){
            return midIndex;
        }else if(key > source[midIndex]){
            return binarySearchRecursive(source, key, midIndex+1, endIndex);
        }else{
            return binarySearchRecursive(source, key, beginIndex, midIndex-1);
        }
        
    }
    
   //循环查找
    public static int binarySearchLoop(int[] source, int key){
        int beginIndex = 0;
        int endIndex = source.length-1;
        
        
        while(true){
            System.out.println("=======");
            if(key<source[beginIndex] || key>source[endIndex] ||  beginIndex>endIndex){  
                return -1;  
            }  
            int midIndex = (beginIndex+endIndex)/2;
            if(key == source[midIndex]){
                return midIndex;
            }else if(key > source[midIndex]){
                beginIndex = midIndex +1;
            }else{
                endIndex = midIndex -1;
            }
        }
        
    }

}

 

方式2:

/** 
     * 普通实现。 
     * @param srcArray 有序数组 
     * @param key 查找元素 
     * @return  不存在返回-1 
     */  
    public static int binSearch(int srcArray[], int key) {  
        int mid;  
        int start = 0;  
        int end = srcArray.length - 1;  
        while (start <= end) {  
            mid = (end - start) / 2 + start;  
            if (key < srcArray[mid]) {  
                end = mid - 1;  
            } else if (key > srcArray[mid]) {  
                start = mid + 1;  
            } else {  
                return mid;  
            }  
        }  
        return -1;  
    }  
	
	
/** 
     * 递归实现。 
     * @param srcArray  有序数组 
     * @param start 数组低地址下标 
     * @param end   数组高地址下标 
     * @param key  查找元素 
     * @return 查找元素不存在返回-1 
     */  
    public static int binSearch(int srcArray[], int start, int end, int key) {  
        int mid = (end - start) / 2 + start;  
        if (srcArray[mid] == key) {  
            return mid;  
        }  
        if (start >= end) {  
            return -1;  
        } else if (key > srcArray[mid]) {  
            return binSearch(srcArray, mid + 1, end, key);  
        } else if (key < srcArray[mid]) {  
            return binSearch(srcArray, start, mid - 1, key);  
        }  
        return -1;  
    }  

 

 

..

 

 

分享到:
评论

相关推荐

    java数组二分查找

    二分查找是一种在有序数组中寻找特定元素的搜索算法,其效率显著高于线性查找。本篇文章将详细探讨Java中的二分查找及其应用。 首先,我们要了解什么是数组。在计算机科学中,数组是一种数据结构,它存储了一组相同...

    函数 实现一个整型有序数组的二分查找

    函数 实现一个整型有序数组的二分查找

    有序数组的折半查找

    折半查找,又称二分查找,是一种在有序数组中查找特定元素的搜索算法。相比传统的顺序查找,它具有更高的效率,尤其是在大型数据集上。折半查找的基本思想是利用数组的有序性,通过每次将查找区间缩小一半来快速定位...

    JS实现二分查找查找有序数组中的数字

    二分查找,也称为折半查找,是一种在有序数组中高效寻找特定元素的搜索算法。在JavaScript中,利用二分查找可以显著提升查找效率,尤其适用于大数据量的处理。二分查找的基本思想是通过不断缩小查找范围,直到找到...

    C#做的有序数组

    查找元素在有序数组中可以通过二分查找法实现,其效率显著高于线性查找。基本步骤包括: 1. 设置查找范围的起始和结束索引。 2. 如果起始索引大于结束索引,表示未找到元素。 3. 否则,计算中间索引,比较中间元素与...

    循环有序数组查找问题1

    【循环有序数组查找问题1】涉及的核心知识点是算法中的二分查找(Binary Search),这是一个在有序数组中查找特定元素的高效方法。对于循环有序数组,虽然整体不是完全有序的,但可以通过巧妙的方法利用二分查找策略...

    文件读出数组进行选择排序和二分查找(java)

    4. **二分查找**:二分查找又称折半查找,是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束;如果目标值大于或小于中间元素,则在数组大于或小于...

    二分查找(Binary Search)是一种在有序数组中查找某一特定元素的搜索算法.txt

    二分查找算法,也称为折半查找算法,是一种在有序数组中查找特定元素的高效搜索方法。该算法的基本思想是通过比较数组中间元素与目标值的大小,将搜索范围缩小到一半,这样每次比较都可以将待查找区间减半,从而达到...

    二分查找.docx 二分查找(Binary Search)是一种在有序数组中查找特定元素的算法 该算法的基本思想是先确定待查找区

    1. **数组必须是有序的**:这是二分查找的前提条件之一,如果数组无序,需要先对数组进行排序。 2. **数据类型**:二分查找适用于数值型数据,对于非数值型数据(如字符串),需要定义合适的比较方法。 3. **边界...

    在数组中快速查找近似值

    二分查找则适用于有序数组。它将数组分成两半,每次比较中间元素与目标值,然后根据比较结果决定在左半部分还是右半部分继续查找。如此反复,直至找到目标值或确定其不存在。二分查找的时间复杂度为O(log n),大大...

    第03章 方法与数组 10 二分查找算法

    二分查找算法,又称折半查找,是一种在有序数组中查找特定元素的高效搜索算法。在计算机科学中,尤其在Java编程中,掌握这种算法对于优化数据处理性能至关重要。本章将深入探讨二分查找的基本原理、实现方式以及其在...

    有序数组中二分查找,快速寻找某个整数是否在序列中

    给定一个单调递增的整数序列,问某个整数是否在序列中。输入样例: 5 1 3 4 7 11 3 3 6 9 输出样例: Yes No No

    深入理解二分查找(一、二分查找及其变体)

    **二分查找(Binary Search)**是一种在有序数组中寻找特定元素的搜索算法。它的基本思想是通过比较中间元素与目标值,不断缩小搜索范围,直到找到目标元素或者确定其不存在。二分查找的时间复杂度为O(log n),在大...

    C+++版二分查找

    二分查找(Binary Search),也称折半查找,是一种在有序数组中查找某一特定元素的搜索算法。该算法的工作原理是通过将目标值与数组中间位置的元素比较来缩小搜索范围,直至找到目标值或确定目标值不存在于数组中。二...

    二分查找 杨辉三角 数组便利

    二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或...

    查找算法集(顺序查找、二分查找、插值查找、动态查找)

    在给定的代码中,二分查找算法函数sq_Dichotomy_Search0实现了有序数组的二分查找。它的参数包括被查找数组、数组元素个数和被查找的关键值。函数返回的值是目标元素在数组中的下标,如果没有找到则返回-1。 插值...

    详解Java数据结构和算法(有序数组和二分查找)

    Java 数据结构和算法:有序数组和二分查找 在 Java 程序设计中,数据结构和算法是非常重要的两个概念。本篇文章主要介绍了有序数组和二分查找的相关知识点。 一、概述 有序数组是一种特殊的数组结构,它的元素...

    Python实现二维有序数组查找的方法

    一种直观的方法是对每一行分别进行二分查找,但这可能会导致效率较低,因为每次只能排除一部分元素,而不能一次性剔除一行或一列。 更好的方法是采用“边界移动”策略。从数组的右上角元素开始,即最大值所在的位置...

    数据结构 二分查找 上机实验

    ### 数据结构之二分查找详解及上机实验 #### 一、引言 在计算机科学领域,二分查找(Binary Search)是一种高效的查找算法,它适用于已排序的数组或列表。该算法通过不断地将查找区间减半来缩小查找范围,从而达到...

Global site tag (gtag.js) - Google Analytics