`

二分查找算法

阅读更多

二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。

 

折半查找,优点:是比较次数少,查找速度快,平均性能好;

缺点:要求待查表为有序表,且插入删除困难。

 

折半查找方法适用于不经常变动而查找频繁的有序列表。

假设表中元素是按升序排列,将表中间位置记录与查找关键字比较,如果两者相等,则查找成功;否则利用中间值将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件值,使查找成功,或直到子表不存在为止,此时查找不成功。

 

查找过程可以分为以下步骤:
 1.从有序数组的中间的元素开始搜索,如果该元素正好是目标元素(即要查找的元素),则搜索过程结束,否则进行下一步。
 2.如果目标元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半区域查找,然后重复第一步的操作。
 3.如果某一步数组为空,则表示找不到目标元素。

 

 // 非递归算法

       public static int binarySearch(int[] arr, int key){

if(arr == null || arr.length == 0){

return -1;

}

int left = 0;

int right = arr.length - 1;

 

while(left <= right){

int mid = (left + right ) / 2;

int midArr = arr[mid];

if(midArr == key){

return mid;

}else if(midArr < key){

left = mid + 1;

}else if(midArr > key){

right = mid - 1;

}else{

return -1;

}

}

return -1;

}

     public static void main(String[] a){

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};

System.out.println(binarySearch(arr, 8));

}  

  

 

 // 递归算法

        function binary_search(arr,low, high, key) {

            if (low > high){

                return -1;

            }

            var mid = parseInt((high + low) / 2);

            if(arr[mid] == key){

                return mid;

            }else if (arr[mid] > key){

                high = mid - 1;

                return binary_search(arr, low, high, key);

            }else if (arr[mid] < key){

                low = mid + 1;

                return binary_search(arr, low, high, key);

            }

        };

        var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];

        var result = binary_search(arr, 0, 13, 10);

        alert(result); // 9 返回目标元素的索引值  

 

--------------------------------------------------------------------------------------------

 

2 二分查找的变种

  关于二分查找,如果条件稍微变换一下,比如:数组之中的数据可能可以重复,要求返回匹配的数据的最小(或最大)的下标;更近一步, 需要找出数组中第一个大于key的元素(也就是最小的大于key的元素的)下标,等等。 这些,虽然只有一点点的变化,实现的时候确实要更加的细心。

 

  二分查找的变种和二分查找原理一样,主要就是变换判断条件(也就是边界条件),如果想直接看如何记忆这些变种的窍门,请直接翻到本文最后。下面来看几种二分查找变种的代码:

 

2.1 查找第一个与key相等的元素

  查找第一个相等的元素,也就是说等于查找key值的元素有好多个,返回这些元素最左边的元素下标。

 

复制代码

// 查找第一个相等的元素

static int findFirstEqual(int[] array, int key) {

    int left = 0;

    int right = array.length - 1;

 

    // 这里必须是 <=

    while (left <= right) {

        int mid = (left + right) / 2;

        if (array[mid] >= key) {

            right = mid - 1;

        }

        else {

            left = mid + 1;

        }

    }

    if (left < array.length && array[left] == key) {

        return left;

    }

    

    return -1;

}

 

2.2 查找最后一个与key相等的元素

  查找最后一个相等的元素,也就是说等于查找key值的元素有好多个,返回这些元素最右边的元素下标。

 

// 查找最后一个相等的元素

static int findLastEqual(int[] array, int key) {

    int left = 0;

    int right = array.length - 1;

 

    // 这里必须是 <=

    while (left <= right) {

        int mid = (left + right) / 2;

        if (array[mid] <= key) {

            left = mid + 1;

        }

        else {

            right = mid - 1;

        }

    }

    if (right >= 0 && array[right] == key) {

        return right;

    }

 

    return -1;

}

 

2.3 查找最后一个等于或者小于key的元素

  查找最后一个等于或者小于key的元素,也就是说等于查找key值的元素有好多个,返回这些元素最右边的元素下标;如果没有等于key值的元素,则返回小于key的最右边元素下标。

 

 

// 查找最后一个等于或者小于key的元素

static int findLastEqualSmaller(int[] array, int key) {

    int left = 0;

    int right = array.length - 1;

 

    // 这里必须是 <=

    while (left <= right) {

        int mid = (left + right) / 2;

        if (array[mid] > key) {

            right = mid - 1;

        }

        else {

            left = mid + 1;

        }

    }

    return right;

}

 

2.4 查找最后一个小于key的元素

  查找最后一个小于key的元素,也就是说返回小于key的最右边元素下标。

 

 

// 查找最后一个小于key的元素

static int findLastSmaller(int[] array, int key) {

    int left = 0;

    int right = array.length - 1;

 

    // 这里必须是 <=

    while (left <= right) {

        int mid = (left + right) / 2;

        if (array[mid] >= key) {

            right = mid - 1;

        }

        else {

            left = mid + 1;

        }

    }

    return right;

}

 

2.5 查找第一个等于或者大于key的元素

  查找第一个等于或者大于key的元素,也就是说等于查找key值的元素有好多个,返回这些元素最左边的元素下标;如果没有等于key值的元素,则返回大于key的最左边元素下标。

 

复制代码

// 查找第一个等于或者大于key的元素

static int findFirstEqualLarger(int[] array, int key) {

    int left = 0;

    int right = array.length - 1;

 

    // 这里必须是 <=

    while (left <= right) {

        int mid = (left + right) / 2;

        if (array[mid] >= key) {

            right = mid - 1;

        }

        else {

            left = mid + 1;

        }

    }

    return left;

}

 

2.6 查找第一个大于key的元素

  查找第一个等于key的元素,也就是说返回大于key的最左边元素下标。

 

 

// 查找第一个大于key的元素

static int findFirstLarger(int[] array, int key) {

    int left = 0;

    int right = array.length - 1;

 

    // 这里必须是 <=

    while (left <= right) {

        int mid = (left + right) / 2;

        if (array[mid] > key) {

            right = mid - 1;

        }

        else {

            left = mid + 1;

        }

    }

    return left;

}

 

3 二分查找变种总结

 

// 这里必须是 <=

while (left <= right) {

    int mid = (left + right) / 2;

    if (array[mid] ? key) {

        //... right = mid - 1;

    }

    else {

        // ... left = mid + 1;

    }

}

return xxx;

 

  二分查找变种较多,不过它们的“套路”是一样的,以上代码就是其套路,如何快速写出二分查找的代码,只需按照以下步骤即可:

 

1 首先判断出是返回left,还是返回right

 

  因为我们知道最后跳出while (left <= right)循环条件是right < left,且right = left - 1。最后right和left一定是卡在"边界值"的左右两边,如果是比较值为key,查找小于等于(或者是小于)key的元素,则边界值就是等于key的所有元素的最左边那个,其实应该返回left。

 

  以数组{1, 2, 3, 3, 4, 5}为例,如果需要查找第一个等于或者小于3的元素下标,我们比较的key值是3,则最后left和right需要满足以下条件:

  我们比较的key值是3,所以此时我们需要返回left。

 

2 判断出比较符号

 

int mid = (left + right) / 2;

if (array[mid] ? key) {

    //... right = xxx;

}

else {

    // ... left = xxx;

}

  也就是这里的 if (array[mid] ? key) 中的判断符号,结合步骤1和给出的条件,如果是查找小于等于key的元素,则知道应该使用判断符号>=,因为是要返回left,所以如果array[mid]等于或者大于key,就应该使用>=,以下是完整代码

 

// 查找小于等于key的元素

int mid = (left + right) / 2;

if (array[mid] >= key) {

    right = mid - 1;

}

else {

    left = mid + 1;

}

分享到:
评论

相关推荐

    二分查找算法流程图流程图举例

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

    二分查找算法及其优化

    二分查找算法是一种高效的数据搜索方法,尤其适用于有序数组或集合。它的基本思想是通过将查找区间不断减半,快速定位目标元素的位置。在每一步中,算法都会比较中间元素与目标值,根据比较结果缩小查找范围。若目标...

    winform 二分查找算法源码

    在IT领域,二分查找算法(也称为折半查找)是一种高效的搜索算法,尤其适用于已排序的数据集合。这种算法利用了有序数据集的特点,通过不断缩小查找范围来快速定位目标值。在本案例中,"winform 二分查找算法源码" ...

    Java 二分查找 算法

    二分查找算法是一种在有序数组中寻找特定元素的搜索算法,其效率远高于线性查找。这个算法基于分治策略,将查找范围不断减半,直到找到目标元素或者确定目标不存在。Java 中实现二分查找的基本步骤如下: 1. 首先,...

    一种改进的二分查找算法

    从提供的文件中,可以挖掘出关于二分查找算法以及其改进方法的详细知识点。下面对这些知识点进行详细阐述: 首先,二分查找算法是一种在有序数组中查找特定元素的高效算法。它通过比较数组中间位置的值与目标值的...

    二分查找算法的C语言版

    ### 二分查找算法的C语言实现 #### 算法概述 二分查找算法(Binary Search)是一种在有序数组中查找特定元素的高效算法。它的工作原理是将目标值与数组中间位置的元素进行比较,如果相等,则查找成功;如果不相等,...

    二分查找算法PPT课件

    二分查找算法,二分查找算法课件,二分查找算法PPT

    分别使用Java和Python实现二分查找算法

    二分查找:分别使用Java和Python实现二分查找算法 二分查找:分别使用Java和Python实现二分查找算法 二分查找:分别使用Java和Python实现二分查找算法 二分查找:分别使用Java和Python实现二分查找算法 二分查找:...

    实验十二------顺序和二分查找算法

    顺序和二分查找算法 顺序查找算法是查找算法中最基本的一种,它的基本思想是从数组的第一个元素开始,一直遍历到最后一个元素,直到找到目标元素或遍历完整个数组。顺序查找算法的实现方法可以使用循环结构,例如...

    java二分查找算法

    ### Java二分查找算法知识点详解 #### 一、二分查找算法概述 二分查找算法是一种在有序数组中查找特定元素的搜索算法。其工作原理是通过将目标值与数组中间元素进行比较来缩小搜索范围,进而达到快速查找的目的。...

    C语言程序设计实现二分查找算法

    在本课程设计报告中,我们将深入探讨如何使用C语言实现二分查找算法。二分查找是一种高效的搜索算法,尤其适用于已排序的数组或列表。它通过不断将搜索区间减半来快速定位目标值,大大提高了查找效率。以下是关于二...

    二分查找算法函数功能: 二分查找

    C 语言中效率最高的查找方式,非常实用。...函数功能: 二分查找 入口参数: 待查找有序表的首地址 int *a 待查找的数据 int num 出口参数: 查找成功返回数据在有序表中的位置0 ~ n-1,不成功返回 -1

    二分查找算法FLASH演示

    二分查找算法,也称为折半查找,是计算机科学中一种高效的搜索算法,尤其适用于已排序的数据集合。这个算法的基本思想是通过不断缩小搜索范围,快速定位目标元素。以下是关于二分查找算法的详细说明: 一、算法原理...

    算法导论二分查找算法

    ### 二分查找算法 #### 一、二分查找算法简介与原理 二分查找算法是一种高效的搜索技术,主要用于在已排序的数组中查找特定元素。该算法的基本思想是在每一步将查找区间减半,直至找到目标元素或者查找区间为空。 ...

Global site tag (gtag.js) - Google Analytics