精华内容
下载资源
问答
  • 二分搜索算法

    2021-01-02 11:38:12
    二分搜索算法二分搜索算法是运用分治策略的一个典型例子。给定已排好序的n个元素arr[0:n-1],现要在这n个元素中找到一个特定元素key。首先我们可以顺序搜索,逐个比较arr[0:n-1]中的元素,直至找出元素x或搜索...

    二分搜索算法


    ​ 二分搜索算法是运用分治策略的一个典型例子给定已排好序的n个元素arr[0:n-1],现要在这n个元素中找到一个特定元素key。首先我们可以顺序搜索,逐个比较arr[0:n-1]中的元素,直至找出元素x或搜索整个数组一遍发现key不再其中。但是这个算法没利用好已排好序这个性质,并且在最坏的情况下,需要O(n)次比较(把整个数组都搜索一遍)。

    ​ 二分搜索方法充分利用了元素间的次序关系,采用了分治策略,可在最坏情况下用O(logn)时间完成搜索任务。二分搜索算法的基本思想是,将n个元素分成个数大致相同的两半,取arr[n/2]与key作比较。如果key=arr[n/2],则找到了key,算法终止;如果key<arr[n/2],则只在数组arr的左半部继续搜索key;如果key>arr[n/2],则只在数组arr的右半部继续搜索key。具体算法程序如下:

    #include<stdio.h>
    
    
    int Binary_Search_(int arr[], int key, int n)
    {
        int left = 0, right = n-1;
        //当区域内的数最左边的数一直小于最右边的(因为是排好序的)
        while(right > left)
        {
            //二分搜索的关键,用于确定要找的数在那个部分
            int middle = (left + right) / 2;
            //如果要找的数刚好在中间,就直接输出
            if(key == arr[middle])
                return middle;
            //如果要找的数在右半部,就把最左边的数指向此时中间数的下一个数
            if(key > arr[middle])
                left = middle + 1;
            else
                right = middle - 1;
        }
    }
    
    
    int main()
    {
        int arr[100], n, key;
        printf("请输入数组长度n: \n");
        scanf("%d", &n);
        printf("请输入数组元素: ");
        for(int i = 0; i < n; i++)
            scanf("%d", &arr[i]);
        printf("请输入你要搜索的数据: ");
        scanf("%d", &key);
        if(!Binary_Search_(arr, key, n))
            printf("要查找的数不再数组里!");
        else
        	//输出要找的数的索引,这里是从0开始,即0~n-1
            printf("要查找的数的序号是: %d\n", Binary_Search_(arr, key, n));
        return 0;
    }
    
    
    
    

    (之后再补充一下二分搜索在其它策略下的解法)
    (如果错误,请在评论区里指正)

    展开全文
  • 算法-二分搜索算法

    2021-05-25 01:33:30
    算法:二分搜索算法(折半查找算法)时间复杂度:二分搜索算法概述二分搜索算法伪代码二分搜索算法实现二分搜索算法概述二分搜索算法,也称折半查找算法,即在一个有序数组中查找某一个特定元素。整个搜索过程从中间...

    算法:二分搜索算法(折半查找算法)

    时间复杂度:

    math?formula=O(log%20%5C%3Bn)

    二分搜索算法概述

    二分搜索算法伪代码

    二分搜索算法实现

    二分搜索算法概述

    二分搜索算法,也称折半查找算法,即在一个有序数组中查找某一个特定元素。整个搜索过程从中间开始,如果要查找的元素即中间元素,那么搜索过程结束;反之根据中间元素与要查找元素的关系在数组对应的那一半查找,例如查找元素大于中间元素,则在整个数组较大元素的那一半查找,反复进行这个过程,直到找到元素,或者数组为空,查找不到元素。

    二分搜索算法描述

    给定一个数组A_0,A_1...A_{n-1}, A_0 \le A_1 \le \cdot \le A_{n - 1},待查找元素为searchnum:

    用left,right分别表示左右端点,即要查找的范围;

    用middle表示中间点,middle = \lfloor (left + right) / 2 \rfloor;

    若left > right,搜索失败;

    若A{middle} > searchnum,right = middle - 1,返回3;

    若A{middle} < searchnum,left = middle + 1,返回3;

    若A{middle} = searchnum,搜索结束,返回middle。

    二分搜索算法伪代码

    while 实现

    BINARY-SEARCH-WHILE(A, searchnum, left, right)

    while left <= right

    middle = (left + right) div 2

    case

    A_middle < searchnum : left = middle + 1

    A_middle > searchnum : right = middle - 1

    A_middle = searchnum : return middle

    return FAILED

    递归实现

    BINARY-SEARCH-RECURSION(A, searchnum, left, right)

    if left <= right

    middle = (left + right) div 2

    case

    A_middle < searchnum :

    return (A, searchnum, middle + 1, right)

    A_middle > searchnum :

    return (A, searchnum, left, middle - 1)

    A_middle = searchnum :

    return middle

    二分查找算法实现

    C

    while 版本

    int binarySearch(arrType * a, arrType searchnum, int left, int right)

    {

    int middle;

    while (left <= right) {

    middle = (left + right) / 2;

    if (a[middle] > searchnum)

    right = middle - 1;

    else if (a[middle] < searchnum)

    left = middle + 1;

    else if (a[middle] == searchnum)

    return middle;

    }

    return -1;

    }

    递归版本

    int binarySearch(arrType * a, arrType searchnum, int left, int right)

    {

    int middle;

    if (left <= right) {

    middle = (left + right) / 2;

    if (a[middle] > searchnum)

    return binarySearch(a, searchnum, left, middle - 1);

    else if (a[middle] < searchnum)

    return binarySearch(a, searchnum, middle + 1, right);

    else if (a[middle] == searchnum)

    return middle;

    }

    return -1;

    }

    Pascal

    外部定义全局变量:

    var

    a : array[1..n] of integer;

    searchnum, result :integer;

    while 版本

    procedure binarySearch(left, right :integer);

    var

    middle : integer;

    begin

    while (left <= right) do

    begin

    middle := (left + right) div 2;

    if (a[middle] > searchnum) then

    right := middle - 1

    else if (a[middle] < searchnum) then

    left := middle + 1

    else

    begin

    result := middle;

    break;

    end;

    end;

    if left > right then

    result := -1;

    end;

    递归版本

    procedure binarySearch(left, right :integer);

    var

    middle : integer;

    begin

    if left <= right then

    begin

    middle := (left + right) div 2;

    if (a[middle] > searchnum) then

    binarySearch(left, middle - 1)

    else if (a[middle] < searchnum) then

    binarySearch(middle + 1, right)

    else

    result := middle;

    end

    else

    result := -1;

    end;

    参考资料

    展开全文
  • 改写二分搜索算法

    2021-10-09 22:44:09
    设array[5]是已排好序的数组,改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。 #include<stdio.h&...

    设array[5]是已排好序的数组,改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。

    #include<stdio.h>
    int BinarySearch(int arr[],int len,int num) {
    	int left = 0;
    	int right = len - 1;
    	if (left == right) {
    		return left;
    	}
    	while (left < right) {
    		int middle = (left + right) / 2;
    		if (arr[middle] == num) {
    			return middle;
    		}
    		else if (arr[middle] < num) {
    			left = middle + 1;
    		}
    		else if (arr[middle] > num) {
    			right = middle - 1;
    		}
    	}
    	return -1;
    }
    void Show(int n,int array[],int length,int number) {
    	if (n == -1){
    		for (int i = 0; i < length; i++) {
    			if (array[i] > number) {
    				int min = i - 1;
    				int max = i;
    				printf("小于x的最大元素位置i为%d\n", min);
    				printf("大于x的最小元素位置i为%d", max);
    				break;
    			}
    		}
    	}
    	else
    	{
    		printf("x的位置是%d", n);
    	}
    
    }
    
    int main() {
    	int array[5] = { 1,3,7,34,56 };
    	int length = 5;
    	int number = 2;
    	int num = BinarySearch(array, length, number);
    	Show(num, array, length, number);
    	return 0;
    }

    展开全文
  • 二分搜索算法题目(参考) 改写二分搜索算法 设a[0:n]是已排好序的数组,请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均...

    二分搜索算法题目(参考)

    改写二分搜索算法
    设a[0:n]是已排好序的数组,请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。

    public class Demo1 {
    
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 10 };
    		int[] array1 = { 1, 3, 4, 5, 6, 7, 8, 9, 10 };
    
    		halfind(array, 9, 6);// i和j相同,均为x在数组中的位置
    //		halfind(array1,9,2);//返回小于x的最大元素位置i和大于x的最小元素位置j
    		
    
    	}
    
    	static void halfind(int array[], int length, int num) {
    		// TODO 自动生成的方法存根
    		int i = 0;
    		int j = length-1 ;//代表的是位置,如果length写的是从0开始,这里就是length.如果是从1开始,这里就是length-1.
    		System.out.println("你想要查找的数字是:"+num);
    
    		// i是左边,j是右边
    		while (i <= j) {
    
    			int middle = (i + j) / 2;// 中间数
    			System.out.println("中间数位置:"+middle);
    			System.out.println("中间数:"+array[middle]);
    			if (num > array[middle]) {
    				i = middle + 1;
    
    			} // 在右边
    			else if (num < array[middle]) {
    				j = middle - 1;
    
    			} // 在左边
    			else if (num == array[middle]) {
    
    				System.out.println("在数组中的位置:" + middle);
    				i = middle;
    				j = middle;
    				break;
    			}
    
    		}
    		if (i != j) {
    			System.out.println(num+"不在列表中!");
    			System.out.println("小于"+num+"的最大元素位置:" + j);
    			System.out.println("大于"+num+"的最小元素位置:" + i);
    		}
    		
    
    	}
    
    }
    
    

    在这里插入图片描述
    在这里插入图片描述

    原二分搜索算法:

    package erfen;
    
    public class test {
    
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		int[] array = { 1, 2, 3, 4, 5 };
    		binarySearch1(array,2,5);
    	}
    
    	private static int binarySearch1(int[] a, int x, int n) {
    		// TODO 自动生成的方法存根
    		int left=0;int right=n-1;
    		while(left<=right) {
    			int middle = (left+right)/2;
    			if(x==a[middle]) {
    				System.out.println("1:"+middle);
    			}
    			if(x>a[middle]) {
    				left=middle+1;
    			}
    			else {//原算法的else也就是这里的,是在右边范围的时候用来最后改变right的值跳出循环的。
    				right = middle-1;
    			}
    		
    		}
    		System.out.println("2:"+left);
    		System.out.println("3:"+right);
    		return -1;
    
    	}
    }
    
    
    展开全文
  • 二分搜索算法详解(Binary Search)

    万次阅读 多人点赞 2020-12-26 20:35:54
    二分搜索(Binary Search) 如何确定一个元素在数组中的位置?(假设数组里面全都是整数) 如果是无序数组,从第0个位置开始遍历搜索,平均时间复杂度:O(n) 如果是有序数组,可以使用二分搜索,最坏时间复杂度为O...
  • 设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。 输入格式: 输入有两行: 第...
  • 算法分析与设计实验报告——二分搜索算法的实现 目录:算法分析与设计实验报告——二分搜索算法的实现一、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色与...
  • #include<iostream> using namespace std; void binarySearch(int a[], int left, int right, int aim) { int i = 0;... //搜索值与中间值相等 if(aim == a[middle]) { i = j = middle.
  • 分治算法-二分搜索算法 分治 首先我们先来介绍以下分治; 分治从字面意思就可以理解,首先是分;将一个待解决的大问题分解为规模较小的子问题,解决子问题。然后是治;治也就是合的意思,将子问题合起来就可以得到...
  • 问题:二分搜索算法 代码1: #include<stdio.h> #include<string.h> int binarySearch(int a[] ,int x, int n){ int left=0; int right=n-1; while(left<=right){ int middle = (left+right)/2;...
  • 算法分析与设计(二、递归与二分搜索算法)1、二分搜索法2、集合划分问题: 1、二分搜索法 二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),...
  • import java.util.Scanner; public class di { public static void main(String[] args) { // TODO Auto-generated method stub Scanner s=new Scanner(System.in); int n=s.nextInt();... int x=s.nextInt();...
  • 2-2 下面的7个算法与本章的二分搜索算法binarySearch略有不同。请判断这7个算法的正确性。如果算法不正确,请说明产生错误的原因;如果算法正确,请给出算法的正确性证明。 (1)与主教材中的算法binarySearch相比...
  • 笔记 二分搜索算法

    2021-05-22 01:32:35
    记录一下二分搜索算法的大概步骤 使用分治的策略 前置条件是数组中的n个元素已经按升序排序
  • 二分搜索算法是运用分治策略的典型例子。 给定已排好序的 n 个元素 a[0:n-1],现要在这 n 个元素中找出一特定元素 x。 首先较容易想到的是用顺序搜索方法,逐个比较 a[0:n-1] 中元素,直至找出元素 x 或搜索遍整个...
  • 搜索具有n个元素有序数组的某个元素时,最直接的方法就是对每个元素进行遍历,也就是线性搜索,时间复杂度为O(n)。 还有一种更高效的搜索方法就是本文要介绍的二分查找,时间复杂度...使用二分查找算法的前提: 查找数
  • #include //二分查找算法int binary(int* arr, int value, int length){int left,right,mid;left = 0;right = length - 1;mid = (left+right)/2;while(left <= right){if(arr[mid] < value){left = mid + 1;}...
  • 二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。 二分查找很好写,却很难写对,据统计只有10%的程序员可以写出没有...
  • 经典算法之二分查找法(俗称二分搜索法) 文章目录经典算法之二分查找法(俗称二分搜索法)前言一、什么是二分查找法?二、代码实现总结 前言 就算法而言,我们主要学习的是数学+思维+逻辑+数据结构实现功能,所以我们...
  • 详解二分查找算法

    2021-03-05 16:28:18
    一、二分查找算法的基本框架 二分查找充分利用了序列元素的递增性质,采用分治策略搜索目标值(目标值存在于序列中),目标值的左边界和右边界(目标值不存在于序列中),其中左边界指的是最大的小于目标值的元素,...
  • 二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列。 该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置...
  • 二分查找算法

    2021-11-15 20:31:37
    1、二分查找算法原理 二分查找算法原理如下: (1)若待查序列为空,则返回-1,并退出算法; (2)若待查序列不为空,则将它的中间元素与目标数值进行比较,判断是否相等; (3)若相等,则返回中间元素索引,并...
  • 二分查找(Binary Search)又称为折半查找,是一种高效的算法二分查找要求待查找列表中的元素是有序的 核心思想 设A[low…high]为当前查找区间,首先确定区间的中点位置mid=⌊(low +high)/2⌋;然后将待查的key...
  • 二分搜索问题 找出最大值和最小值 时间复杂度O(n) using System; using System.Collections.Generic; namespace dataLearn { class Program { static void Main(string[] args) { List<int> list = ...
  • 实现二分搜索的递归与非递归程序,跟踪分析执行过程,体会两者的执行效率,分析算法复杂性。 二、实验环境: VS2019 – c++文件(只要能运行cpp文件都可以) 三、算法描述及实验步骤 1.算法思想: 又叫折半查找...
  • 二分查找又叫折半查找,是一种简单又快速的查找算法;它对要查找的序列有两个要求:一是该序列必须是有序的,即该序列中所有元素都是按照大小关系排好顺序的,升序和降序都可以,二是该序列必须是顺序存储的. 算法...
  • 二分查找算法例题

    千次阅读 2021-04-21 14:26:32
    目录一、问题描述二、实现思路三、解题代码四、运行结果 一、问题描述   对于给定11个数据...  对于给定11个数据元素的有序表:(2,3,10,15,20,25,28,29,30,35,40),采用二分查找,若查找给定值为20的

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 270,390
精华内容 108,156
关键字:

二分搜索算法