The authors introduce ： Hello, friends. I'm Muxi Xi , You can call me Xiaomu
Author URI ： Muxi Xi's personal blog home page .
The author's gitee：https://gitee.com/muxi-c-language
C Language series ：
1. Do you really know these knowledge points of circular sentences ？（1）
2. Can you branch statements ？
3. .C Language lesson 5 .
4. C Language lesson 4 .
Xiao Mu likes editing as much as her friends , Code every day 🤭, Indulge in learning , Getting thinner . It's a great honor to share what I've learned , Make progress with you , Become a qualified volume King . If there are mistakes in the article , Welcome to the comments section ️ correct . So start today's study ！

1. Preface

Binary search is an algorithm , The input is a An ordered list of elements （ It has to be orderly ）️, If the element you are looking for is included in the list , Binary search returns its position , Otherwise return to NULL（ Null pointer ）. for example ： There is an array to store 1~100, Randomly choose one of the numbers （ Assuming that 60）, You need to guess the number I choose with the least number of times , After every guess , I'll tell you it's big , Small and right . This is a very traditional search method , Too many tests , Too complicated , Then there is the binary search method .

2. Dichotomy search

“ Two points search “ Also called half 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 . The search process starts with , Suppose the elements in the table are in ascending order , Compare the keywords recorded in the middle of the table with the search keywords , If the two are equal , Then the search is successful ; Otherwise, use the middle position record to divide the table into front 、 Last two sub tables , If the key of the intermediate location record is greater than the search key , Then look up the previous sub table , Otherwise, look up the next sub table .

for example ：
An ordered array stores 1~10, Set the number to be searched as 7.

int arr[] = {
     1,2,3,4,5,6,7,8,9,10 };
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	int mid=left+(right-left);// In this way, in order to prevent overflow due to excessive value 

The first is when you are judged to have guessed big ： here right The subscript of becomes mid-1,left unchanged

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

When the second situation is judged to be small ,mid The subscript becomes mid+1,left The subscript does not change .

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

The third case is when arr[mid] When searching for the value , Print subscripts directly

if（arr[mid]==k)
    printf(" eureka , Subscript to be ：>%d",mid);

Code implementation ：

#include<stdio.h>
int main()
{
    
	int arr[] = {
    0,1,2,3,4,5,6,7,8,9};
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	int key = 7;
	int mid = 0;
	while (left <= right)
	{
    
		mid = (left + right) / 2;
		if (arr[mid] > key)
		{
    
			right = mid - 1;
		}
		else if (arr[mid] < key)
		{
    
			left = mid + 1;
		}
		else
			break;
	}
	if (left <= right)
		printf(" eureka , The subscript is :>%d\n", mid);
	else
		printf(" Can't find \n");
}

Thus, a simple binary search problem of an ordered array is realized .
What if I write a function about binary search ？
Code ：

 If you implement a binary lookup function ：
int bin_search(int arr[], int left, int right, int key)
{
    
      int mid = 0;
     while(left<=right)
     {
    
         mid = (left+right)>>1;
         if(arr[mid]>key)
         {
    
             right = mid-1;
         }
         else if(arr[mid] < key)
         {
    
             left = mid+1;
         }
         else
             return mid;// eureka , Returns the subscript 
         }

3. At the end

So that's all for today's study . Friends who think it's good can pay attention to , Like or collect ！ Thank you for your support . The following code, I hope you guys can test it by yourself , After all, hands-on operation makes the memory more profound .

Yours ️ Praise is the source of my creative power
Your collection is the direction of my struggle
Your attention is my greatest support
Yours ️ Comments are a bright light for me to move forward
It's not easy to create , I hope you can support Xiaomu

See you in the next issue ！