Dichotomy search (C language)

Finding this work is the operation we often have to do with a pile of data , As we know, the time complexity of sequential search will greatly increase when there is more data, which will seriously affect the running speed of our program , So is there an algorithm with excellent time complexity to solve this problem —— Two points search
Let's first talk about what is binary search , Let's see how its manual process is realized .
Binary search is to increase the original linear time to logarithmic time , It greatly shortens the time to find the target data , But the biggest disadvantage of binary search is that the data to be checked must be orderly , That is to say, when we use binary search, we should first sort our data , Sorting is inherently time-consuming , So when we choose sorting algorithms, we should choose ones with less time complexity, such as quick sort and heap sort , In this article, I will use quick sort to prepare for binary search , Students who are not very familiar with quick sorting can see my previous article .
Let's take a look at the manual process of binary search , To fully understand how this binary search reduces the time complexity of the program .

With this process, programming becomes very simple ：

int binarySearch(int *array, int count, int targetNum) {
    
	int head;
	int tail;
	int middle;

	head = 0;
	tail = count + 1;
	middle  = (head + tail) / 2;

	while (head < tail) {
    
		if (array[middle] < targetNum) {
    
			head = middle;
			middle = (head + tail) / 2;			
		} else if (array[middle] > targetNum) {
    
			tail = middle;
			middle = (head + tail) / 2;
		} else if (array[middle] == targetNum) {
    
			return middle;
		}
	}

	return NOT_FOUND;
}

Now we put the whole code into the program , Take a look at the complete code ：

#include <stdio.h>
#include <malloc.h>
#include <time.h>

#include "tool.h"

int *creatarrayay(int minValue, int maxValue, int count);
void showarrayay(int *array, int count);
void swapOnce(int *array, int start, int end);
void quickSort(int *array, int count);
int binarySearch(int *array, int count, int targetNum);

int binarySearch(int *array, int count, int targetNum) {
    
	int head;
	int tail;
	int middle;

	head = 0;
	tail = count + 1;
	middle  = (head + tail) / 2;

	while (head < tail) {
    
		if (array[middle] < targetNum) {
    
			head = middle;
			middle = (head + tail) / 2;			
		} else if (array[middle] > targetNum) {
    
			tail = middle;
			middle = (head + tail) / 2;
		} else if (array[middle] == targetNum) {
    
			return middle;
		}
	}

	return NOT_FOUND;
}

void quickSort(int *arrayay, int count) {
    
	swapOnce(arrayay, 0, count-1);
}

void swapOnce(int *arrayay, int start, int end) {
    
	int i = start;
	int j = end;
	int temp = arrayay[i];

	if (i >= j) {
    
		return;
	}

	while (i < j) {
    
		while (i < j && arrayay[j] > temp) {
    
			j--;
		}
		if (i < j) {
    
			arrayay[i++] = arrayay[j];
		}

		while (i < j && arrayay[i] < temp) {
    
			i++;
		} 
		if (i < j) {
    
			arrayay[j--] = arrayay[i];
		}
	}

	arrayay[i] = temp;

	swapOnce(arrayay, start, i - 1);
	swapOnce(arrayay, i + 1, end);
}

void showarrayay(int *arrayay, int count) {
    
	int index;

	for(index = 0; index < count; index++) {
    
		printf("[%d] ",arrayay[index]);
	}

	printf("\n");
}

int *creatarrayay(int minValue, int maxValue, int count) {
    
	int index;
	int value;
	int *arrayay;

	srand(time(0));
	arrayay = (int *) calloc(sizeof(int), count);
	for (index = 0; index < count; index++) {
    
		value = rand() % (maxValue - minValue + 1) + minValue;
		arrayay[index] = value;
	}

	return arrayay;
}

int main() {
    
	int *array = NULL;
	int maxValue;
	int minValue;
	int count;
	int index;
	int targetNum;
	
	printf("please input minValue/maxValue/count:"); 
	scanf("%d%d%d", &minValue, &maxValue, &count);
	array = creatarrayay(minValue, maxValue, count);
	
	printf("after sorting:\n");
	quickSort(array, count);
	showarrayay(array, count);

	printf("input targetNum:");
	scanf("%d",&targetNum);

	index = binarySearch(array, count, targetNum);
	if (NOT_FOUND == index) {
    
		printf("Not found!\n");
	} else {
    
		printf("At : %d\n", index + 1);
	}
	
	free(array);

	return 0;
}

int *creatarrayay(int minValue, int maxValue, int count);
void showarrayay(int *array, int count);

The first function is to input the maximum value of the array , The minimum value and the size of the array can automatically generate an array , It saves us the trouble of inputting data frequently ;
The second is to print the array on the screen .

void swapOnce(int *array, int start, int end);
void quickSort(int *array, int count);

This is the function of quick sort .

Now let's take a look at the operation of the program and the results


notes ：tool.h

#ifndef _TOOL_H_
#define _TOOL_H_

typedef unsigned char boolean;

#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1


#endif

Thank you for reading ！