Find a specific number in an ordered array (binary search or half search)

Specific ideas

Binary search only applies to An increasing or decreasing array , Here we are unified as an increasing array , below , Let's briefly introduce the specific idea of binary search . Give the following array {1,2,3,4,5,6,7,8,9,10}. Their subscript is 0~9, We need to find in this set of arrays Numbers 7. First search for , The average value of the sum of the leftmost and rightmost subscripts is 4, We locked the number 5, because 5 Than 7 Small , So the number we are looking for can only be 5 To the right of ,5 The number on the left can be ignored . Second search , Numbers 6 And number 10 The average value of the sum of subscripts of is 7, We locked the number 8, because 8 Than 7 Big , So the number you are looking for can only be 8 Left side . Then we go on The third search …… Find the number 7 In the process of , We only used four searches , It can be seen that the efficiency is much higher than ordinary search .

Code implementation

int main()
{
    
	int arr[] = {
     1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = sz - 1;
	int k = 7;

	while (left <= right)
	{
    
		int mid = (left + right) / 2;

		if (arr[mid] < k)
		{
    
			left = mid + 1;
		}

		else if (arr[mid] > k)
		{
    
			right = mid - 1;
		}

		else if (left = right)
		{
    
			printf(" eureka , The subscript is %d\n", mid);
			break;
		}
	}

	return 0;
}

Running results