# C语言基础之二分查找知识最全汇总

## 二、原始二分查找

1.在有序数组中寻找一个数所在下标。

`int main(){    int arr[] = {1,2,3,4,5,6,7,8,9};    int left,right,fin;    fin = 3;    left = 0;right = sizeof(arr)/sizeof(arr[0])-1;    while(left <= right) {        int mid;        mid = (left+right) / 2;        if (arr[mid] == fin) {            printf("找到了：%d\n", mid);            return 0;        }        if (mid < fin)            left = mid+1;        else if (mid > fin)            right = mid-1;    }    printf("没找到");    return 0;}`

## 三、二分查找的变化之数组元素重复

1.返回匹配数key的最小下标

`#include <stdio.h>int main() {    int arr[] = {1,3,3,3,3,4,5,6,7};    int left,right,lenght,key;    key = 3;    left = 0;    lenght = sizeof(arr)/sizeof(arr[0]);    right = lenght -1;    while(left <= right){        //等于的条件不能忽略        int mid = (left+right)/2;        if (arr[mid] < key)            left = mid + 1;            //目的是用left来寻找key点，不考虑mid = key的情况        else            right = mid - 1;    }    if ((left < lenght)&&(arr[left] == key))        printf("%d\n",left);    return 0;}`

2.返回匹配数的最大下标

`#include <stdio.h>int main() {    int arr[] = {1,3,3,3,3,4,5,6,7};    int left,right,lenght,key;    key = 3;    left = 0;    lenght = sizeof(arr)/sizeof(arr[0]);    right = lenght -1;    while(left <= right){        int mid = (left+right)/2;        if (arr[mid] <= key)            left = mid + 1;        else            right = mid - 1;    }    if ((right >= 0)&&(arr[right] == key))        printf("%d\n",right);    return 0;}`

3.返回第一个大于匹配数的下标

`#include <stdio.h>int main() {    int arr[] = {1,1,1,1,1,4,5,6,7};    int left,right,lenght,key;    key = 3;    left = 0;    lenght = sizeof(arr)/sizeof(arr[0]);    right = lenght -1;    while(left <= right){        int mid = (left+right)/2;        if (arr[mid] < key)            left = mid + 1;        else            right = mid - 1;    }        printf("%d\n",arr[left]);    return 0;}`

4.查找某个数的出现次数

## 四、轮转循环

（其实把它理解成为一个分段函数最容易，但是csdn不好写数学表达式，不好画图，有兴趣的蒟蒻可以私信我）

`#include <stdio.h>int find(int arr[],int left,int right,int key) {//传参a[]是所求数组，left,right为所求左右下标，key是所求元素    while (left <= right) {        int mid = (left + right) / 2;        if(arr[mid] > key){            if(arr[mid] < arr[right])//当此式成立时表明元素顺序起点在mid左边。                right = mid - 1;            else {//元素顺序起点在mid右边，但是key有可能在mid左边有可能在mid右边                if (key > arr[left])//在左边                    right = mid - 1;                else                    left = mid + 1;            }        }        else if(arr[mid] < key){            if(arr[mid] > arr[left])//在mid左边是递增的（顺序起点在[0]或右边）                left = mid + 1;            else{//顺序起点在左边且不在[0]上                if (key > arr[right])//在mid左边                    right = mid - 1;                else                    left = left + 1;            }        }        else//当相等时直接返回mid           return mid;    }}int main() {    int left,right,key,mid;    int arr[] = {7,8,9,0,1,2,3,4,5,6};    left = 0;    right =( sizeof(arr)/sizeof(arr[0]) ) - 1;    key = 4;    mid = find(arr,left,right,key);    printf("峡谷吴彦祖 %d",mid);    return 0;}`

## 五、杨氏矩阵

`int yang_matrix_2(int arr[X][Y],int num) {    int x = 0;    int y = Y;    int a = x;    int b = y;    do{       a = x;b = y;        if (arr[x][y] > num) {//在列上进行折半查找            int left = 0;            int right = Y-1;            while (left <= right){                int mid = (((left ^ right) >> 1)+(left & right));                if (arr[x][mid] > num)                    right = mid - 1;                else {                    if (arr[x][mid] < num)                        left = mid + 1;                    else                        return 1;}            }            y = left;            x--;        }        else{            if(arr[x][y] < num){                int left = 0;                int right = X-1;                while (left <= right){                    int mid = (((left ^ right) >> 1)+(left & right));                    if (arr[mid][y] > num)                        right = mid - 1;                    else {if (arr[mid][y] < num)                            left = mid + 1;                        else                            return 1;}                }                x = right;                ++y;            }//在行上进行折半查找            else                return 1;        }    }while ((x != a) && (y != b));    return 0;}`