Binary Search in C++: Ascending + Descending Ordered Arrays

Question

So I am trying to make a binary sort algorithm for my c++ class, but I keep getting a segmentation fault when my binarySearch function runs. No matter how hard me and my roommate look at it, we cant find the issue. Any help would be greatly appreciated.

int binarySearch(int arr[], int k, int first, int last)
{
    if(arr[first] <= arr[last])
    {
        int mid = (first + last) / 2;

        if(k == arr[mid])
        {
            return mid;
        }
        else if (k < arr[mid])
        {
            return binarySearch(arr, k, first, mid-1);
        }
        else return binarySearch(arr, k, mid+1, last);
    }   
    else if(arr[first] >= arr[last])
    {
        int mid = (first + last) / 2;

        if(k == arr[mid])
        {
            return mid;
        }
        else if (k < arr[mid])
        {
            return binarySearch(arr, k, mid+1, last);
        }
        else return binarySearch(arr, k, first, mid-1);
    }
    else return -1;
}

After fixing the segmentation fault, I noticed I must have an error somewhere in my logic because the program keeps outputting that the key was unable to be found even though it exists in the array.

Answer 1

Your code works actually, if the element you are searching for is in the array. However, it does not catch incorrect input.

When calling the function, make sure that:

• first and last are between 0 and (array length - 1)
• first < last

eg: if the array has 10 elements, first and last must be between 0 and 9.

Try this:

int main() {
    int a[] = {134, 232, 233, 234, 587, 623, 793, 802, 963, 1074};
    int b[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int na = binarySearch(a, 587, 0, 9);
    int nb = binarySearch(b, 3, 0, 9);

    printf("na: %d\n", na);  // prints 'na: 4'
    printf("nb: %d\n", nb);  // prints 'nb: 7'
}

If the element you are searching for is not in the array, then the recursion does never terminate, you can fix that by adding the following to the head of binarySearch():

if (first == last && k != arr[first])
    return -1;

Answer 2

Not a major concern, but to prevent overflow it is usual to rewrite int mid = (first + last) / 2; as int mid = first + (last-first)>>1; It also seems that you will never hit the line return -1 (the first two conditionals take care of all possible orderings)

An implementation (for strictly increasing, or decreasing array) could look like that

#include <cassert>

int binarySearch(int* array, int k, int l, int h, bool asc)
{
    if (l>h)
        return -1;
    int m = l + ((h - l) >> 1);
    if (array[m] == k)
        return m;
    else
    {
        if (array[m]>k)
            return binarySearch(array, k, (asc ? l : m + 1), (asc ? m - 1 : h),asc);
        else
            return binarySearch(array, k, (asc ? m + 1 : l), (asc ? h : m - 1),asc);
    }
}

int main()
{
    int ascArray[7] = {1, 2, 3, 4, 5, 6, 7};
    int descArray[7] = {7, 6, 5, 4, 3, 2, 1};
    assert(binarySearch(ascArray, 7, 0, 6, ascArray[0] < ascArray[1]) == 6);
    assert(binarySearch(descArray, 7, 0, 6, descArray[0] < descArray[1]) == 0);
}

Answer 3

Make sure first>=last. I think the crash is because you don't find the element in the array.

Answer 4

instead of using if else if, you can try while loop:

int mid = (first + last)/2;
while(first<=last && arr[mid]!=k){
    if(arr[mid]<k)
        first=mid+1;
    else
        last=mid-1;
    mid = (first + last)/2;

}
if(arr[mid] == k){
    std::cout<<"Found"<<std::endl;
}else{
    std::cout<<"Not Found"<<std::endl;
}

Instead you can use vector, that makes it very easy:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){

int arrint[] = {3,5,2,1,7,6,9,4,8,10};
vector<int> vector1(arrint,arrint+10);

sort(vector1.begin(),vector1.end());
int n;
cout<<"Enter element to search: ";
cin>>n;
cin.ignore();
cout<<endl;

if(binary_search(vector1.begin(),vector1.end(),n)){
    cout<<"Found: "<<n<<endl;
}else{
    cout<<n<<" Not Found"<<endl;
}


//cin.get();
return 0;
}