算法学习（一）——二分查找递归方法

二分查找算法：

在有序数组a中查找值b，从数组a的中间值a[mid ]开始查找，若b比a[ mid ]小，则从 [0,mid-1 ]区间重新开始上述操作，若b比a[ mid ]大，则从 [mid+1，length-1 ]区间重新开始上述操作直到找到b或找遍数组也无该值

数组必须有序，才可用二分查找：

c语言实现

 1 #include<stdio.h>
 2 #include<malloc.h>
 3 int rank(int m,int a[],int hi,int lo);
 4 int main()
 5 {
 6 int n,m,i,*a,lo,hi,temp;
 7 scanf("%d %d",&n,&m);
 8 a=(int*)malloc(sizeof(int)*n);
 9 for(i=0;i<n;i++)
10 scanf("%d",&a[i]);
11 hi=n-1;
12 lo=0;
13 temp=rank(m,a,hi,lo);
14 if(temp==-1)
15 printf("未找到！");
16 else
17 printf("%d在数组第%d个",m,temp+1); 
18 return 0;
19 } 
20 //递归 
21 int rank(int m,int a[],int hi,int lo)
22 {
23 int mid=(hi-lo)/2+lo;
24 if(mid<0) return -1;
25 else if(a[mid]==m) return mid;
26 else if(a[mid]<m) return rank(m,a,hi,mid);
27 else if(a[mid]>m) return rank(m,a,mid,hi);
28 }

python实现：

 1 #!/usr/bin/env python3
 2 # -*- coding: utf-8 -*-
 3 # _author: Stranger
 4 # date: 2018/7/4
 5 
 6 
 7 # 输入函数
 8 def inp():
 9     arr = input('请输入有序数组:').split(' ')
10     arr = list(map(int, arr))
11     m = int(input('请输入要查找的值：'))
12     return arr, m
13 
14 
15 # 二分实现
16 def div(n, arr=[]):
17     length = len(arr)
18     count = 0
19     mid = (length-1)//2
20     min_a = 0
21     max_a = length-1
22     for i in range(length):
23         temp = mid
24         count += 1
25         if arr[mid] > n:
26             mid = (min_a + max_a) // 2
27             max_a = temp - 1
28         elif arr[mid] < n:
29             mid = (mid + max_a) // 2
30             min_a = temp + 1
31 
32         else:
33             print("成功找到该值, 索引值为：", mid+1, "查找：", count)
34             break
35     print(length)
36     if i == length-1:
37         print("该值不存在")
38 
39 
40 if __name__ == '__main__':
41     array, m = inp()
42     div(m, array)

python实现