Skip to content

Instantly share code, notes, and snippets.

@nvjkmr
Created October 27, 2016 10:56
Show Gist options
  • Save nvjkmr/2a2071ad9543c3c463446cfc1aae2f53 to your computer and use it in GitHub Desktop.
Save nvjkmr/2a2071ad9543c3c463446cfc1aae2f53 to your computer and use it in GitHub Desktop.
Divide and conquer search for sorted integer array
/* Divide and conquer search for sorted integer array.
* Pre: Takes array pointer
* Integer to find
* Last index of array
* Initial of array
* Return: Index of the array
*/
int divideAndConquer(int* arr, int toFind, int lastIndex, int initialIndex) {
int mid = initialIndex + ((lastIndex - initialIndex) / 2);
if(*(arr+mid) == toFind) {
printf("%d is equal to %d mid: %d\n", toFind, *(arr+mid), mid);
return mid;
} else if(*(arr+mid) < toFind) {
printf("%d is greater than %d mid: %d\n", toFind, *(arr+mid), mid);
// find between mid & length
return divideAndConquer(arr, toFind, lastIndex, mid+1);
} else if(*(arr+mid) > toFind) {
printf("%d is less than %d mid: %d\n", toFind, *(arr+mid), mid);
// find between 0 & mid
return divideAndConquer(arr, toFind, initialIndex, mid-1);
}
return -1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment