directory

Binary search algorithm definition

Analysis of binary search algorithm

Time complexity of binary search algorithm

The average search length of a binary search

General algorithm of binary search

Binary search function recursive algorithm

Hello! Hello, everyone, I am trying to make money to buy hair water gray little ape, recently in the development of the time accidentally used before the binary search algorithm on the data structure, so here and we simply share the binary search algorithm for a variety of languages.

So what is a binary search algorithm?

 

Binary search algorithm definition

The so-called binary search algorithm, also known as half search, is generally applicable to array elements, specifically, the array elements have been stored in order. It is a highly efficient search algorithm, which can obtain the element sequence or search times by half-searching the order list.

 

Analysis of binary search algorithm

We assume that the elements in the existing linear table are arranged in ascending order. The idea of binary search algorithm is to compare the size of the middle element of the table being searched with that of the element to be searched. If the size is equal, the location or search times of the element will be output.

If the intermediate element is not equal to the searched element, the linear table is divided into two parts of the linear table with the intermediate element. If the intermediate element is smaller than the searched element, the binary query is performed on the linear table with the latter part again.

On the contrary, if the middle element is greater than the searched element, the same binary search is performed on the previous part of the linear table. When the middle element is equal to the searched element, the search ends. Or until the linear table can no longer be divided, the search ends, this indicates that the table does not have the element.

The following is a search diagram for binary search algorithms:

 

Time complexity of binary search algorithm

The basic idea of binary search is that an array A with n elements in ascending order is divided into two parts which are roughly equal before and after. The middle element A [n/2] is compared with the searched element (M). If M =a[n/2], m is found and the algorithm stops.

If m<a[n/2], the binary search for M continues only in the left half of array A, and if m>a[n/2], the binary search for M continues in the right half of array A. The search ends when m=a[n/2] or the array is no longer divisible.

 

So the time complexity is the number of while loops,

I have n elements,

The number of elements searched at each time is n, n/2, n/4,…. n/2^k

If I have n lookups, so I find the element on my first lookups, then I have 1. So I have k plus 1.

N /2 to the k is greater than or equal to 1

If n / 2 ^ (k) = 1

So k is equal to log base 2 of n.

So the time complexity can be expressed as O(h)=O(log base 2n).

 

The average search length of a binary search

Let the element to be searched be n, then the average search length of a half-split search is:

 

General algorithm of binary search

The following is a functional method for binary search,

The arguments passed in are the ascending array and the element to be searched. If the element was found, the number of searches is returned, otherwise -1 is returned.

int binary_search(int[] a, int value)
{
        int low = 0;

        int high = a.length - 1;

        while (low <= high)

        {

            int middle = (low + high) / 2;

            if (a[middle] == value)

            {

                return middle;

            }

            if (value < a[middle])

            {

                high = middle - 1;

            }

            else

            {

                low = middle + 1; }}return -1;

    }
Copy the code

 

Binary search function recursive algorithm

The arguments passed are the incrementing array, the value to look for, the start search position (default: 0), and the end search position (default: array length).

int binary_search_ecursion(int a[],int value,int low,int high) {
	int middle=0;
	if(low<=high)
	{		
		middle = (low+high)/2;
		if (a[middle]==value) {
			return middle;
		}else {
			if (a[middle]<value) {
				return binary_search_ecursion(a, value, middle+1, high);
			}
			else {
				return binary_search_ecursion(a, value, low, middle-1); }}}return -1;
}
Copy the code

The binary search method of thinking is applicable to any language that requires sequential list search, and the basic idea is the same. The binary lookup function above is based on C# and can be extended.

 

Find it useful rememberThumb up attentionHey!

Meanwhile, if you like Python, you can follow my wechat official account “Grey Wolf Hole Owner” and reply to “Python Notes” to get the sharing of notes and quick reference manual of common functions and methods from beginner to master of Python!

Big bad Wolf is looking forward to progress with you!