[C language] binary search (half search)

Table of Contents

Binary search

1. Introduction

2. Example

3. The code is as follows

4. Summary

binary search

1.Introduction

binary search also has special cases, such as the sequence itself is ordered.How did this ordered sequence come about?Sometimes it may be sorted itself, or it may be obtained by a sorting algorithm.

No matter what else happens, let's assume that the array is ordered, and then the binary search should come on stage.

Binary Search is also known as halved search.Binary search has two requirements, one is that the sequence is ordered, and the other is that the sequence uses an ordered storage structure (such as an array).

2.Example

Not much nonsense, let's go directly to the example:

Assume a sorted set of numbers {5,12,15,19,22,35,36,40,67,78,82}

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

As shown in Figure 1, we first find the subscripts of the first and last numbers of this group of numbers, define the first number as left, and the last number as right, and then find the subscript of the middle element mid = left +(left+right) / 2, then mid=35, compare mid=35 with k=40, find mid

So it can be determined that if there is a keyword 40 in the array, it must exist in the middle of the area pointed to by mid and right.

When traversing again, the positions of left and mid need to be updated, so that left is moved to the next position of mid (that is, the position of mid+1), and at the same time, mid is re-pointed to the middle position of left and right.As shown in Figure 2:

Similarly, comparing mid with k, 67 < 40, so it can be determined that if 40 exists, it must be in the area pointed to by left and mid.So let right point to a position to the left of the mid position (that is, the position of mid-1), and update the position of mid at the same time, as shown in Figure 3:

Similarly, compare mid with k, 36 > 40, so it can be determined that if 40 exists, it must be in the area pointed to by mid and right.So let left point to a position on the right side of the mid position (that is, the position of mid+1), and update the position of mid at the same time, as shown in Figure 4:

When the 4th judgment is made, it is found that mid is the keyword 21, and the search ends

Note: In the process of searching, if the middle position of left and right is in the middle of the two keywords during the calculation, the midThe position is not an integer and needs to be rounded uniformly.

3. The code is as follows

#includeint 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 the length of the arrayint left = 0;//The first digitint right = sz - 1;//the last digitwhile (left <= right){int mid = left + (right - left) / 2;if (arr[mid] < k)//Remove the left array{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("Cannot find the number\n");}return 0;}

4.Summary

By comparing the average search length of the split-half search, compared with the sequential search, it is obvious that the split-half search is more efficient.However, the halved search algorithm is only applicable to ordered table, and it is limited to the lookup table represented by a sequential storage structure.

Finally, the article ends here!