二分查找和排序

柔光的暖阳◎ 2022-05-14 15:25 244阅读 0赞

二分查找，主要是针对排序问题进行查找

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_27_color_FFFFFF_t_70][]我们先算出数组的长度

len = sizeof(a) / sizeof(a[0])

我们先设置

int left = 0;
    int right = Len - 1;
    int mid = (left + right ) / 2;

如果K大于mid，那么 left = mid + 1;

小于 right = mid -1;

#include <stdio.h>
    
    int search( int key, int a[], int len )
    {
    	int k;
    	//scanf("%d", &k );
    	k = 99;
    	int left = 0;
    	int right = len - 1;
    	int ret = -1;
    	while ( right >= left )
    	{
    		int mid = ( left + right ) / 2;
    		if ( a[mid] == k )
    		{
    			ret = mid;
    			break;
    		} else if ( a[mid] > k )
    		{
    			right = mid - 1;
    		} else {
    			left = mid + 1;
    		}
    	}
    	return ret;
    }
    
    int main()
    {
    	int a[] = {1,3,5,7,8,9,11,34,56,65,67,88,99};
    	int len = sizeof(a) / sizeof(a[0]);
    	int respond = 0;
    	respond = search( 7, a, len );
    	printf("%d\n",respond);
    	return 0;
    }

那么如果我们碰到不是按顺序排列的数组，如何办呢？

我们可以先排序然后再进行二分查找

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_27_color_FFFFFF_t_70 1][]找到最大的数，然后和最后一个数进行swap，重复进行就行了。

#include <stdio.h>
    
    int max( int a[], int len )
    {
    	int maxid = 0;
    	for ( int i = 1; i < len; i++ )
    	{
    		if ( a[i] > a[maxid] )
    		{
    			maxid = i;
    		}
    	}
    	return maxid;
    }
    
    int main()
    {
    	int a[] = {2,45,6,8,7,23,67,98,24,65,11,22,32};
    	int len = sizeof(a)/sizeof(a[0]);
    
    	for ( int i = len - 1; i > 0; i-- )
    	{
    		int maxid = max( a, i + 1 );
    		//swap a[maxid, a[len - 1]
    		int t = a[maxid];
    		a[maxid] = a[i];
    		a[i] = t;
    	}
    
    	for ( int i = 0; i < len; i++ )
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    	return 0;
    }

完整的代码为

#include <stdio.h>
    
    int max( int a[], int len )
    {
    	int maxid = 0;
    	for ( int i = 1; i < len; i++ )
    	{
    		if ( a[i] > a[maxid] )
    		{
    			maxid = i;
    		}
    	}
    	return maxid;
    }
    
    int search( int key, int a[], int len )
    {
    	int k;
    	scanf("%d", &k);
    	int left = 0;
    	int right = len - 1;
    	int ret = -1;
    	while ( right >= left )
    	{
    		int mid = ( left + right ) / 2;
    		if ( a[mid] == k )
    		{
    			ret = mid;
    			break;
    		} else if ( a[mid] > k )
    		{
    			right = mid - 1;
    		} else {
    			left = mid + 1;
    		}
    	}
    	return ret;
    }
    
    int main()
    {
    	int a[] = {1,2,3,4,5,66,54,22,43,78,21,23,24,42};
    	int len = sizeof(a) / sizeof(a[0]);
    
    	for ( int i = len - 1; i > 0; i-- )
    	{
    		int maxid = max( a, i + 1 );
    		int t = a[maxid];
    		a[maxid] = a[i];
    		a[i] = t;
    	}
    
    	for ( int i = 0; i < len; i++ )
    	{
    		printf("%d ",a[i] );
    	}
    	printf("\n");
    
    	int respond = 0;
    	int k;
    	printf("input you want to know element: \n");
    	respond = search(k, a, len );
    	printf("the way is: %d\n", respond );
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_27_color_FFFFFF_t_70]: /images/20220503/5c84c2d5dd3d482ca80ec009a1f73a3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_27_color_FFFFFF_t_70 1]: /images/20220503/5f9480f08d3943fd9595bae010169d2b.png