C language practice - binary search (half search)

Catalog

Two points search

1. brief introduction

2. Example

3. The code is as follows

4. summary

---

Two points search

1. brief introduction

Two points search There are also special circumstances , For example, the sequence itself is ordered . How does this ordered sequence come into being ？ Sometimes it may be ordered by itself , It may also be obtained by sorting algorithm .

Regardless of other circumstances , Let's assume that this array is ordered , Next, it's time for two-point search .

Two points search （Binary Search） It is also called half search . Binary search has two requirements , One is that the sequence of numbers is orderly , The other is that the sequence uses a sequential storage structure （ For example, array ）.

2. Example

I don't say much nonsense , Direct example ：

Suppose a set of numbers that have been sorted {5,12,15,19,22,35,36,40,67,78,82}

Suppose the element we are looking for is k=40;

  Pictured 1, We first find the subscript of the first number and the last number of this group , Define the first as left, The last number is right, Then find the subscript of the intermediate element mid = left + (left+right) / 2, be mid=35, hold mid=35 And k=40 Compare , Find out mid<k And the array is sorted in ascending order ,

So we can decide if there is 40  This keyword , It must exist in mid  and right  In the middle of the area .

  It needs to be updated when traversing again left  and mid The location of , Make left  Move to mid In the next position （ That is to say mid+1 Location ）, At the same time mid Point back to left  and right  In the middle of . Pictured 2 Shown ：

Again , use mid  Same as k  The comparison ,67 < 40, So we can judge 40  If there is , Must be in left  and mid  In the area you're pointing to . So make right  Point to mid Position a position on the left ( That is to say mid-1 Location ), Simultaneous updating mid The location of , Pictured 3：

  Again , use mid  Same as k  The comparison ,36 > 40, So we can judge 40  If there is , Must be in mid  and right  In the area you're pointing to . So make left  Point to mid A position on the right side of the position （ That is to say mid+1 Location ）, Simultaneous updating mid The location of , Pictured 4：

When the first 4 When making judgment for the first time , Find out mid It's keywords 21 , Find the end

Be careful ： In the process of searching , If left  and right  The middle position of is in the middle of two keywords during calculation , That is to seek mid The position of is not an integer , We need to do rounding operations in a unified way .

3. The code is as follows

#include<stdio.h>
int main()
{
	int arr[] = { 5,12,15,19,22,35,36,40,67,78,82 };
	int k;
	scanf("%d", &k);
	int sz = sizeof(arr) / sizeof(arr[0]);// Find array length 
	int left = 0;// The first number 
	int right = sz - 1;// Last digit 
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] < k)// Remove the array on the left 
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)// Remove the array on the right 
		{
			right = mid - 1;
		}
		else
		{
			printf(" Find the number , The subscript is ：%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf(" The number cannot be found \n");
	}

	return 0;
}

4. summary

By comparing the average search length of half search , Compare with sequential search , Obviously, the efficiency of half search is higher . But the half search algorithm is only applicable to Ordered list , At the same time, only the look-up table is represented by the sequential storage structure .

Last , This concludes the article ！