数据结构 -- 查找之二分法查找

素颜马尾好姑娘i 2022-08-25 10:54 237阅读 0赞

有序数组的二分法查找：

1.递归 二分法查找；

2,非递归 二分法查找；

以下代码 在vs2010 测试通过：

#include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    //非递归法 二分法查找
    int unrecursive_binary_search(int *arr,int arrLength,int value){
    	
    	int low,high,mid;
    	low = 0;
    	high = arrLength-1;
    	mid = (low+high)/2;
    
    	while(low <= high){
    		if(arr[mid] > value){
    			high = mid-1;
    			mid = (low+high)/2;
    		}else if(arr[mid] < value){
    			low = mid+1;
    			mid = (low+high)/2;
    		}else{
    			return mid;
    		}
    	}
    	if(low > high){
    		return -1;
    	}
    }
    //递归法 二分查找
    
    int recursive_binary_search(int *arr,int low,int high,int value){
    	
    	int mid;
    	mid = (low+high)/2;
    
    	if(low <= high){
    		if(arr[mid] > value){
    			recursive_binary_search(arr,low,mid-1,value);
    		}else if(arr[mid] < value){
    			recursive_binary_search(arr,mid+1,high,value);
    		}else{
    			return mid;
    		}
    	}else{
    		return -1;
    	}	
    }
    
    int _tmain(int argc, _TCHAR* argv[]){
    	int arr[] = {0,1,16,24,35,47,59,62,73,88,99};
    	int result1,result2 ;
    	int length;
    
    	length = sizeof(arr)/sizeof(int);
    	//二分法 的递归查找
    	result1 = recursive_binary_search(arr,0,length-1,62);
    	if(result1 != -1){
    		printf("递归法 查找成功!\n");
    	}else{
    		printf("该值不存在!\n");
    	}
    	//二分法的非递归查找
    	result2 = unrecursive_binary_search(arr,length,62);
    	if(result2 != -1){
    		printf("非递归法 查找成功!\n");
    	}else{
    		printf("该值不存在!\n");
    	}
    	system("pause");
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，237人围观）

还没有评论，来说两句吧...

相关阅读

相关【二分法查找】

使用二分法查找需要注意的点：使用二分法的前提：数组为有序数组，同时题目还强调数组中无重复元素。二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变

快来打我*/ 2023年10月16日 12:19/ 0 赞/ 62 阅读

相关数据结构 -- 查找之二分法查找

有序数组的二分法查找： 1.递归二分法查找； 2,非递归二分法查找；以下代码在vs2010 测试通过： include "stdafx.h" i

素颜马尾好姑娘i/ 2022年08月25日 10:54/ 0 赞/ 238 阅读

相关二分法查找

package com.abstractdatatype.search; /二分法查找/ public class BinarySearch {

亦凉/ 2022年08月13日 15:54/ 0 赞/ 224 阅读

相关二分法查找

public static int binarySearch(int[] a,int x,int n) { int left=0,right=n-1;

ゝ一纸荒年。/ 2022年06月07日 03:36/ 0 赞/ 216 阅读

相关数据结构之查找

常见查找算法顺序查找二分查找索引查找 hash查找主关键字:不能重复,唯一,比如id 次关键字:可能重复,比如姓名查找表:

怼烎@/ 2022年03月30日 15:06/ 0 赞/ 321 阅读

相关二分法查找

package com.test; import java.util.Arrays; import java.util.Random; import j

男娘i/ 2022年03月20日 11:56/ 0 赞/ 269 阅读

相关二分法查找

package day01.happensbefore; / @author ZerlindaLi create at 2019/5/27

- 日理万妓/ 2022年01月27日 16:23/ 0 赞/ 278 阅读

相关数据结构之查找

本次主要包含内存中的查找有：顺序查找，折半查找，分块查找，二叉排序树查找，哈希表查找 1）顺序查找：是最简单的查找方式，如，a= \{45,53,12,3,37,24,90,

àì夳堔傛蜴生んèń/ 2022年01月07日 10:05/ 0 赞/ 226 阅读

相关二分法查找

二分法查找当线性表中数据元素是按大小排列存放时，可以改进顺序查找算法，以得到更高效率的新算法——二分法 (折半查找)。 ![这里写图片描述][SouthEast]

电玩女神/ 2021年09月14日 15:00/ 0 赞/ 491 阅读

相关二分法查找

一参考文档 [https://zhangjia.io/959.html][https_zhangjia.io_959.html] [https://zhidao.baid

本是古典何须时尚/ 2021年07月25日 01:10/ 0 赞/ 461 阅读