写代码可以在整型有序数组中查找想要的数字， 找到了返回下标，找不到返回-1.（折半查找）

运行环境  win10  vs2013

实现数查找功能:给定一个有序的数组(升序),给定一个数字,查找这个数字的下标

{1,2,3,4,5}升序

{5,4,3,2,1} 降序

{5,3,,4,2,1}无序

假设{1,2,3,4,5}数字4的下标为3

#include<stdio.h>
#include<stdlib.h>
int main(){
	int arr[] = { 1, 2, 3, 4, 5 };
	int to_find = 4;  //假设要求取4的下标
	int i = 0;
	for (; i < sizeof(arr) / sizeof(arr[0]); i++){ //用来求数组中元素的个数
		if (to_find == arr[i]){
			break;
		}
	}
	//找到了(i<5)
	if (i == 5){
		printf("没有找到预期元素\n");
	}
	else{
		//找到了
		printf("找到了!下标为 %d\n", i);
	}
	system("pause");
	return 0;
}

 

       但是现在有一个问题,当前数组是一个有序数组,要找到某个元素需要依次遍历一边才能找到,因此我们可以引进二分查找,也叫折半查找,这样就能快速提高代码的执行效率

下面是用折半查找实现

 

#include<stdio.h>
#include<stdlib.h>
int main(){
	int arr[] = { 1, 2, 3, 4, 5 };
	int to_find = 4;  //假设要求取4的下标
	//定义查找区间比如[0,4]计算平均值即可
	//不用纠结于是偶数个还是奇数个,大致的中间值即可
	//[0,4]=>2
	//[2,4]=>3
	int left = 0;
	int  mid = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1; //right表示最后一个元素的下标,因此要-1
	while (left <= right){   // 由于[left,right]闭区间,若为<,就会导致left和right重合时,循环无法完成
		mid = (left + right) / 2;  //mid用来表示下标,也表示临界值
		if (to_find <arr[mid]){
			right = mid - 1;//去掉临界值
		}
		else if (to_find>arr[mid]){
			left = mid + 1;
		} else{
			break;
		}
	}
		if (left <= right){
			printf("找到了!下标为: %d\n", mid);
		}else{
			printf("没找到\n");
		}
	system("pause");
	return 0;
}

  注:应聘时较大几率会遇到该题!