4. Binary search

Catalog

Traverse

Two points search

Principle demonstration

Code section

---

arr[]={1,2,3,4,5,6,7,8,9,10}, How to find numbers 7？

Traverse

utilize for loop , From the subscript for 0 Start looking for the number of , When the cycle reaches the seventh , Find the number 7.

When the number of numbers in the array is uncertain , Can pass sizeof To calculate .sizeof（arr） What I want is the size of the entire array ,sizeof（arr[0]） What we need is the size of the first element , Unit is byte . Divide the former by the latter , Get the number of numbers .

// Traverse 
#include<stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int input = 0;
	scanf("%d", &input);
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (i = 0; i < sz; i++)
	{
		if (arr[i] == input)
		{
			printf(" eureka , Subscript to be %d\n", i);
			break;
		}
	}
	return 0;
}

utilize for Loop traversal seems to solve this kind of problem , But if 1~10000 Find a certain number in , If one by one traversal seems to be a waste of time , Now let's introduce binary search .

Two points search

Binary search is also called binary search （Binary Search）, It is an efficient search method . however , Half search requires that the linear table must use Sequential storage structure , And the elements in the table are arranged in order by keywords .

Be careful ： The premise of binary search must be An orderly sequence of numbers ！！！
 

Principle demonstration

Find the subscript of the element ： utilize sizeof, adopt sizeof(arr) / sizeof(arr[0]) Count the number of elements , Because the subscript of an array is from 0 At the beginning , Reduce the result by 1, Is the subscript number of the last element .

Record the median ： Set two variables left、right To lock our subscript range , utilize (right-letf)/2 To find the median . Each time the range is gradually reduced by hours ,left、right The corresponding subscript range should also be updated .

initialization ： take left Lower calibration is 0,right Subscript positioning 9.

First search for ： Judge left、righ The middle number of and 7 Size ：5<7, take left Moved to 5+1.

 

Second search ： Judge left、righ The middle number of and 7 Size ：8>7, take right Moved to 8-1 It's about .

 

 

The third search ： Judge left、righ The middle number of and 7 Size ：6<7, take right Moved to 6+1 It's about .

  Fourth search ： Judge left、righ The middle number of and 7 Size ：7=7, eureka .

Code section

The search process is in the main function ：

// Two points search 

#include<stdio.h>

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int input = 0;
	scanf("%d", &input);
	int left = 0;
	int right = sz-1;
	int mid = 0;
	while (left <= right)
	{
		mid = left+(right - left) / 2;
		if (arr[mid] < input)
		{
			left = mid + 1;
		}
		else if (arr[mid] > input)
		{
			right = mid - 1;
		}
		else
			break;
	}

	if (arr[mid] == input)
		printf(" eureka , The subscript is %d\n", mid);
	else
		printf(" Did not find \n");

	return 0;
}

The lookup process is in the function ：

#include<stdio.h>

void check(int sz,int* arr,int input)//int* arr And int arr[] Agreement , It is the address of the first element of the array 
{
	int left = 0;
	int right = sz - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (arr[mid] < input)
		{
			left = mid + 1;
		}
		else if (arr[mid] > input)
		{
			right = mid - 1;
		}
		else
			break;
	}
	if (arr[mid] == input)
		printf(" eureka , The subscript is %d\n", mid);
	else
		printf(" Did not find \n");
}

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int input = 0;
	scanf("%d", &input);
	check(sz, arr, input);
	return 0;
}