# C binary search algorithm

• 2020-05-30 20:50:32
• OfStack

C classic algorithm 2 - point search method

1. Find the location of the array according to key

``````
#include <stdio.h>
/*
key = 9;
1 2 3 4 5 6 7 8
arr 3 .  4 .  5 .  7 .  9  .  11 .  21 .  23
low = 1  mid = (low + high)/2 = 4      high = 8;
one   arr[mid] = 7 < 9;  so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
two   arr[mid] = 11 > 9  so low = 5 ,   high = mid - 1 = 5 mid = 5;
arr[mid] = 9 == key

if(key = 10) low = mid + 1 > high

*/
int main(int argc, const char * argv[])
{
int findByHalf(int arr[], int len, int key);

int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
int len = sizeof(arr)/sizeof(int);

int index = findByHalf(arr, len, 88);

printf("index = %d\n", index);
return 0;
}

int findByHalf(int arr[], int len, int key){
int low = 0;
int high = len - 1;

int mid ;

while(low <= high){
mid = (low + high) / 2;
// The right to find
if (key > arr[mid]) {
low = mid + 1;
// On the left to find
}else if (key > arr[mid]) {
high = mid - 1;
}else{
return mid;
}

}
return -1;
}

``````

2. Insert a number to get its position in the array

``````
#include <stdio.h>
/*
key = 9;
1 2 3 4 5 6 7 8
arr 3 .  4 .  5 .  7 .  9  .  11 .  21 .  23
low = 1  mid = (low + high)/2 = 4      high = 8;
one   arr[mid] = 7 < 9;  so low = mid + 1 = 5; high = 8; mid = (low + high)/2 = 6
two   arr[mid] = 11 > 9  so low = 5 ,   high = mid - 1 = 5 mid = 5;
arr[mid] = 9 == key

if(key = 10) low = mid + 1 > high

*/
int main(int argc, const char * argv[])
{
int findByHalf(int arr[], int len, int key);

int arr[] = {3, 4 , 5, 7, 9 , 11, 21, 23};
int len = sizeof(arr)/sizeof(int);

int index = findByHalf(arr, len, 88);

printf("index = %d\n", index);
return 0;
}

int insertByHalf(int arr[], int len, int key){
int low = 0;
int high = len - 1;

int mid ;

while(low <= high){
mid = (low + high) / 2;
// The right to find
if (key > arr[mid]) {
low = mid + 1;
// On the left to find
}else if (key > arr[mid]) {
high = mid - 1;
}else{
// if arr[mid] == key
// the key Insert it after this number
return mid + 1;
}

}
// if low > high  instructions  key > arr[mid];
// the key Inserted into the low The corresponding   The position of this number
return low;
}

``````