算法图解笔记 Day 1
简单查找
准确的说就是傻找
更佳的查找方式————二分查找
二分查找的输入是一个有序的元素列表一般而言，对于包涵n个元素的的列表，用二分查找最多需要log（2，n）步，而简单查找最多需要n步。
二分查找的代码实现（python）
def binary_search(list,item
):
small
= 0
big
= len(list) - 1
while(small
<= big
):
mid
= (small
+ big
)/2
guess
= list[mid
]
if guess
== item
:
return mid
elif guess
> item
:
big
= mid
- 1
else:
small
= mid
+1
return None
————————————————————————————
c语言版
#include<stdio.h>
int main()
{
int target
= 2;
int nums
[5] = {1,2,3,4,5};
int right
= sizeof(nums
)/sizeof(nums
[0]) - 1;
int left
= 0;
int mid
= 0;
while(left
<= right
)
{
mid
= left
+ (right
- left
)/2;
if (nums
[mid
] == target
)
{
printf("%d", mid
);
break;
}
else if(nums
[mid
] < target
)
{
left
= mid
+ 1 ;
}
else if(nums
[mid
] > target
)
{
right
= mid
- 1 ;
}
}
return 0;
}
查找左边界（c语言版）
#include<stdio.h>
int main()
{
int target
= 100;
int nums
[9] = {1,2,4,4,5,56,67,89,99};
int right
= sizeof(nums
)/sizeof(nums
[0]) - 1;
int left
= 0;
int mid
= 0;
while(left
<= right
)
{
mid
= left
+ (right
- left
)/2;
if (nums
[mid
] == target
)
{
right
= mid
- 1;
}
else if(nums
[mid
] < target
)
{
left
= mid
+ 1 ;
}
else if(nums
[mid
] > target
)
{
right
= mid
- 1 ;
}
}
if(left
>= sizeof(nums
)/sizeof(nums
[0]) || nums
[left
] != target
){
printf("error");
}
else{
printf("%d",left
);
}
return 0;
}
