二分查找---折半查找

#include<iostream>
using namespace std;
//二分查找算法---返回查找到的元素的下标
//数组 数组长度 查找的值
int test(int arr[],int len,int val)
{
	//判断传入的数组值是否合法
	if (len < 1)
	{
		return -1;
	}
	//最小值和最大值
	int low = 0;
	int high = len - 1;
	//
	while (low <= high)
	{
		int mid = (low + high) / 2;
		//判断查找元素值比中间元素值大还是小
		if (val > arr[mid])
		{
			low = mid + 1; //那么要去比mid大的左边区间进行折半查找，需要把最小值更新到mid+1
		}
		if (val < arr[mid])
		{
			high = mid - 1;//那么要去比mid小的右边区间进行折半查找，需要把最大值更新到mid-1
		}
		if (val == arr[mid])
		{
			return mid; //返回的就是查找到的元素下标
		}
	}

}
int main()
{
	int arr[8] = { -1,0,1,2,3,4,10,12};
	int num=test(arr,8,4);
	cout << "4元素在数组中下标位置为：" << num << endl;
	system("pause");
	return 0;
}

#include<iostream>
using namespace std;
//二分查找算法---返回查找到的元素的下标
//数组 数组长度 查找的值
int test(int arr[],int len,int val)
{
	//判断传入的数组值是否合法
	if (len < 1)
	{
		return -1;
	}
	//最小值和最大值
	int low = 0;
	int high = len - 1;
	//
	while (low <= high)
	{
		int mid = (low + high) / 2;
		//判断查找元素值比中间元素值大还是小
		if (val > arr[mid])
		{
			low = mid + 1; //那么要去比mid大的左边区间进行折半查找，需要把最小值更新到mid+1
		}
		if (val < arr[mid])
		{
			high = mid - 1;//那么要去比mid小的右边区间进行折半查找，需要把最大值更新到mid-1
		}
		if (val == arr[mid])
		{
		//mid值要大于最小值的下标，判断mid前面是否有与val值相等的元素
			while (mid > low && arr[mid - 1] == val)//在不越界的前提下后一个值与前一个值相等
			{
				--mid;//下标减一
			}
			return mid; //返回的就是查找到的元素下标
		}
	}

}
int main()
{
	int arr[9] = { -1,1,1,2,3,4,4,10,12};
	int num=test(arr,8,4);
	cout << "4元素在数组中下标位置为：" << num << endl;
	system("pause");
	return 0;
}

#include<iostream>
using namespace std;
//二分查找算法---返回查找到的元素的下标
//数组 数组长度 查找的值
int test(int arr[],int len,int val,int low,int high)
{
	//判断传入的数组值是否合法
	if (len < 1)
	{
		return -1;
	}
	//
	int mid = -1;
	//
	if (low <= high)
	{
		mid = (low + high) / 2;
		//判断查找元素值比中间元素值大还是小
		if (val > arr[mid])//要去mid右边，即比左边比mid大的区间
		{
			//这里如果在大区间里面找到了val的位置，就会返回下标，用mid来接收
			//没有找到返回-1
			mid=test(arr, len, val, mid + 1, high);
		}
		if (val < arr[mid])//要去mid左边，即比左边比mid小的区间
		{
			//这里如果在小区间里面找到了val的位置，就会返回下标，用mid来接收
			mid=test(arr, len, val, low, mid - 1);
		}
		if (val == arr[mid])
		{
			while (mid > low && arr[mid - 1] == val)//在不越界的前提下后一个值与前一个值相等
			{
				--mid;//下标减一
			}
			return mid; //返回的就是查找到的元素下标
		}
	}
	  //元素不在当前区间数组中
		return mid;
}
int main()
{
	int arr[9] = { -1,1,1,2,3,4,4,10,12};
	int num=test(arr,9,4,0,8);
	cout << "10元素在数组中下标位置为：" << num << endl;
	system("pause");
	return 0;
}