辗转相除法求最大公约数

对于x,y,假设它俩有一个最大公因数T,则(nx+my)%T==0

原因:x=T+T+T+T+T····· y=T+T+T+T+T······

x/y=v······w

-->x=v*y+w

-->w=1x+(-v)y 即x%y的余数也能够被最大公因数整除

x>y-->x=x%y y-->y=y%x

#include<stdio.h>
int main()
{
    int x = 75, y = 100;
    int z = 0;
    while (z = x % y)
    {
        x = y;
        y = z;
    }
    printf("%d", y);
    return 0;
}

使用二分查找法在整形有序数组中查找某个数

!!!使用二分查找法必须要是有序数组

第一点:首先要确定数组的长度,使用sizeof(arr) / sizeof(arr[0])来确定

第二点:最左边下标为start,最右边为end,中间为 int min=(start+end)/2

第三点:判断这个数(a)和二分排序法确定的中间数(mid)的大小

​ 若a > arr[mid]---->则a的下标与数组左半边无关系,即start = mid+1

​ 若a < arr[mid]---->则a的下标与数组右半边无关系,即start = mid-1

#include<stdio.h>

int main()
{
    int arr[] = { 1,5,8,42,55,67,78,82,93,130 };
    int c = sizeof(arr) / sizeof(arr[0]);
    int a = 130;
    int start = 0, end = c - 1;
    while (1) 
    {
        int mid = (start + end) / 2;
        if (a > arr[mid])
        {
            start = mid+1;  
        }
        else if(a < arr[mid])
        {
            end = mid-1;
        }
        else
        {
            printf("%d", mid);
            break;
        }
    }
    return 0;
}