Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "C language half search how to achieve". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. Topic description

N ordered integer sequences have been placed in an one-dimensional array, and the binary search method is used to find the position of integer m in the array.

If found, output its subscript value; otherwise, output "Not be found!" .

two。 Analysis of problems

Binary search (also known as half-and-half search) is essentially a kind of divide-and-conquer algorithm.

The so-called divide-and-conquer algorithm refers to divide and conquer, that is, the larger-scale problem is divided into several smaller-scale problems, these sub-problems are independent of each other and the same as the original problem, and the whole problem can be solved by solving the smaller-scale problem.

The divide-and-conquer method in which the problem is divided into two smaller problems is called dichotomy. It should be noted that the binary search method is only applicable to ordered sequences.

The basic idea of binary search is to determine the scope of the array before each search, assuming the pointers low and high (lowhigh), and the search ends.

3. Algorithm design

N ordered numbers should be stored in the array. According to the value range of the subscript of the array, it is known that the initial values of pointers low and high are 0 and Nmurl, respectively.

In addition to the three pointer variables low, high, and mid, a variable (assuming k) is needed to record the subscript, and the value of the variable k is used to determine whether the integer is in the given array. Below we use a schematic diagram to show the process of binary search.

Suppose the ordered number stored in an one-dimensional array is listed as 5 13 19 21 37 56 64 75 80 88 92, and the integer m to be found is 21.

According to the binary search method, pointers low and high initially point to elements 5 and 92, respectively, known by mid= (low+high) / 2, and pointer mid points to element 56. The schematic diagram is as follows:

The integer 21 represented by the variable m is compared with the element 56 pointed by the pointer mid. 21 is less than 56. According to the binary search algorithm, the search scope is now narrowed to the front of the element pointed by the pointer mid, that is, from 5 to 37.

The pointer high, which originally pointed to the element with the subscript Nmur1, now points to the element with the subscript mid-1, and then recalculates the subscript of the element that the pointer mid refers to.

Compare again, 21 is greater than 19, and now the comparison range is again transferred to the end of the element referred to by mid, and the subscript of the element referred to by the low element is changed from 0 to mid+1.

The value of the element referred to by the current mid is 21, which is the same as the integer value you are looking for, so the lookup is successful, and the sequence number of the checked element is equal to the value of the pointer mid in the table.

4. Moving picture demonstration

Dynamic graph analysis

5. Code implementation

Flow chart design

Complete code

# include # define N 10int main () {int a [N] = {- 3 for 4, 7, 7, 13, 45, 67, 89100180}; int low = 0; int high = N-1; int mid; int i; int m; int k =-1; printf ("the data in the an array are as follows:"); for (I = 0; I

< N; i++) { printf("%d ", a[i]); } printf("\n"); printf("Enter m："); scanf("%d", &m); while (low a[mid]) { low = mid + 1; } else { k = mid; break; } } } if (k >

= 0) printf ("masking% d index=%d\ n", m, k); else printf ("Not be found!\ n");}

Running result

Code map

Program analysis

There are two situations in which the loop ends in the above procedure.

One is because the decision condition of the cycle low = 0) printf ("% m% d index=%d\ n", m, k); else printf ("Not be found!\ n"); return 0;}

Running result

This is the end of the content of "half search in C language". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.