递归1--二分查找

递归1--二分查找

一、心得

递归的时候注意返回值,返回的时候是返回到上一层

二、代码及结果

 1 /*
 2 二分查找:
 3 可写递推和递归
 4 其实这两个都只要把递推式子写出来就好
 5
 6 查找的数大于mid,left=mid+1
 7 小于mid,right=mid-1
 8 边界条件,等于mid,输出即可
 9 */
10 /*
11 心得:注意返回值,返回的时候是返回到上一层
12 */
13 #include <iostream>
14 using namespace std;
15 //二分查找递归,设置标签
16 bool binarySearch1(int a[],int left,int right,int num){//初始left=0,right=length-1
17     bool flag=false;
18     int mid=(left+right)/2;
19     //cout<<mid<<endl;
20     //cout<<num<<" "<<a[mid]<<endl;
21     if(left<=right){
22         if(num==a[mid]) {
23             flag=true;
24         }
25         else if(num>a[mid]){
26             //cout<<"right:"<<a[mid+1]<<" "<<a[right]<<endl;
27             flag=binarySearch1(a,mid+1,right,num);
28
29         }
30         else if(num<a[mid]){
31             //cout<<"left:"<<a[left]<<" "<<a[mid-1]<<endl;
32             flag=binarySearch1(a,left,mid-1,num);
33         }
34     }
35     return flag;
36 }
37
38 //二分查找非递归,不设置标签
39 /*
40 不设置返回值的时候,有栈可以存值
41 */
42 bool binarySearch2(int a[],int left,int right,int num){//初始left=0,right=length-1
43
44     int mid=(left+right)/2;
45     //cout<<mid<<endl;
46     //cout<<num<<" "<<a[mid]<<endl;
47     if(left<=right){
48         if(num==a[mid]) {
49             return true;
50         }
51         else if(num>a[mid]){
52             //cout<<"right:"<<a[mid+1]<<" "<<a[right]<<endl;
53             binarySearch2(a,mid+1,right,num);
54
55         }
56         else if(num<a[mid]){
57             //cout<<"left:"<<a[left]<<" "<<a[mid-1]<<endl;
58             binarySearch2(a,left,mid-1,num);
59         }
60     }
61     else{
62         return false;
63     }
64 }
65
66
67 //二分查找递推
68 bool binarySearch3(int a[],int left,int right,int num){//初始left=0,right=length-1
69     while(left<=right){
70         int mid=(left+right)/2;
71         if(num==a[mid]) return true;
72         else if(num>a[mid]) left=mid+1;
73         else if(num<a[mid]) right=mid-1;
74     }
75     return false;
76 }
77
78 int main(){
79     int a[11]={1,2,4,7,8,9,11,15,17,19,20};
80     //bool b=binarySearch1(a,0,10,20);
81     //bool b=binarySearch2(a,0,10,7);
82     bool b=binarySearch3(a,0,10,20);
83     cout<<b<<endl;
84     return 0;
85 } 

时间: 06-15

递归1--二分查找的相关文章

关于递归与二分查找技术

简单的说,递归就是函数自己调用自己.在数据结构里面会经常使用递归,因为递归代码比较简洁优雅,易懂. 编写递归程序时主要注意三点 (1)递归总有一个最简单的情况,方法的第一条语句总是包含return的条件语句 (2)递归调用总是去尝试解决一个规模更小的子问题,这样递归才能收敛到最简单的情况.在下面代码中,第四个参数和第三个参数的差值一直在缩小 (3)递归调用的父问题和尝试解决的子问题之间不应该有交集.在如下代码中,两个子问题,各自操作的数组部分是不同的 下面是二分法查找的递归实现和非递归实现: 特

递归实现二分查找

#!/usr/bin/env python # -*- coding: utf-8 -*- # @Time : 2018-01-31 20:29 # @Author : hhj# @Site : # @File : 递归实现二分查找.py# def func(arg1,arg2,stop):# if arg1==0:# print(arg1,arg2)# arg3=arg1+arg2# print(arg3)# if arg3<stop:# func(arg2,arg3,stop) #递归###

递归和非递归的二分查找

思路很简单,代码注释已标注 #include <stdio.h> //递归二分查找 int binarySearch(int*start,int *end,intfindData){ if (start > end) {      // 递归边界条件 return -1; } int *mid = start + (end - start)/2;     //根据中间值不断二分缩小待查元素所在范围 if (findData == *mid) { return *mid; }else if

4-8日 递归和二分查找

1,递归函数 在函数中调用函数本身自己.执行一次开辟一个空间,python对你的内存有一个保护机制,默认只能递归到998层. def func(n): n += 1 print(n) func(n) func(0) 2,二分查找 二分查找前提是有序且唯一的数字列表. li = [1,21,30,32,44,55,56,433,] def search(num,l,start=None,end=None): start = start if start else 0 end = end if en

day_06、递归、二分查找

递归 递归意味着调用自身. 递归函数通常包括以下俩部分. 基线条件:(针对最小的问题)满足这个条件是将直接返回一个值. 递归条件:包含一个或多个调用,这些调用旨在解决问题的一部分. 1 def fun(n): 2 if n == 1: 3 return 1 4 else: 5 return n * fun(n-1) 乘阶 1 def fun(n, x): 2 if x == 0: 3 return 1 4 else: 5 return n * fun(n, x-1) 幂 1 def fun(n)

Python——递归、二分查找算法

递归函数 1. 递归 (1)什么是递归:在函数中调用自身函数(2)最大递归深度:默认997/998--是Python从内存角度出发做的限制 n = 0 def story(): global n n+= 1 print(n) story() #997/998 story() (3)修改最大深度:最好不要改--递归次数太多,则不适合用递归解决问题 import sys sys.setrecursionlimit(2000) #1997/1998 2. 递归的优点 会让代码变简单 3. 递归的缺点

递归与二分查找

# 斐波那契数列1 1 2 3 5 8 13 def func(n): print(n) if n==1 or n ==2: return 1 else: return func(n-1) + func(n - 2) print(func(6)) # result:8 # 函数在执行递归的过程中,如果获取不到结果会将当前状态进行存储,继续向下递归直到返回结果,python中的递归深度为997-998. # 递归解析 # 第一次递归进入执行执行func(6 - 1),没有结果继续向下执行func(

冒泡排序、递归、二分查找

冒泡排序:给出一个纯数字列表. 请对列表进行排序. 思路: 1.完成a和b的数据交换. 例如, a = 10, b = 24 交换之后, a = 24, b = 102.循环列表. 判断a[i]和a[i+1]之间的大小关系, 如果a[i]比a[i+1]大. 则进行互换. 循环结束的时候. 当前列表中最大的数据就会被移动到最右端. 3.想一想, 如果再次执行一次上面的操作. 最终第二大的数据就移动到了右端. 以此类推. 如果反复的进行执行相应的操作. 那这个列表就变成了一个有序列表. li=[11

二分查找(递归与非递归)

递归的二分查找: 1 int search(int *a, int target, int p, int r) 2 { 3 if (p <= r) 4 { 5 int mid; 6 7 mid = (p + r) / 2; 8 if (*(a + mid) == target) 9 return 1; 10 else if (*(a + mid) > target) 11 return search(a, target, p, mid - 1); 12 else 13 return searc

(续)二分查找(不用递归)

接着上一篇,其实不用递归进行二分查找也很简单,当时咋就没想起来呢.. OK废话少说, show me the code 1 #include <stdio.h> 2 3 int binary_search_no_recursion(int a[], int left, int right, int key){ 4 while(left<=right){ //attention!!! 5 int mid = (left+right)/2; 6 if(key > a[mid]) 7 l