C语言实现——二分查找_c语言数据结构实验报告二分查找

一、二分查找介绍

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且每次比较都使搜索范围缩小一半。

二、两种方法及思路

二分查找的思路非常简单，在一个有序数组里面查找一个元素，通过一个中间值，将元素分为两半，如果中间值不是想要查找的元素，就和查找的元素比较，如果查找的元素大于中间值，就在数组的后半部分查找。如果查找的元素小于中间值，就在数组的后半部分查找。每次查找都会使查找的范围缩小一半。

主要难点就是如何确定二分查找的边界，这里给出了两种方法，一种方法是left<=right，相当于是左闭右闭区间，其中的每一个元素都要使用到。另一种方法是left<right，相当于是左闭右开区间，其中right是边界，不能取元素比较。

三、代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
 
int BinarySearch1(int* arr, int len, int x) {
 
	int left = 0, right = len - 1;
 
	while (left <= right)
	{
		int mid = left + (right-left) / 2; // 防止数组过大造成整数越界
		if (arr[mid] == x) {
			return mid;  // 找到了目标值
		}
		else if (arr[mid] > x) {
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
 
	return -1; // 未找到目标值
}
 
int BinarySearch2(int* arr, int len, int x) {
 
	int left = 0, right = len;
 
	while (left < right)
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] == x) {
			return mid;  // 找到的目标值
		}
		else if (arr[mid] > x) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
 
	return 0; // 未找到目标值
}
 
int main() {
	
	int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
	int index = -1;
	index = BinarySearch1(arr, 10, 3);
	printf("%d\n", index);
 
	index = BinarySearch2(arr, 10, 6);
	printf("%d\n", index);
 
	return 0;
}

四、运行结果