Coding Chalenge #10 Binary Search

Programming: Principles and Practice Using C++
Chapter 26: Testing

So if I'm not mistaken, the idea of a binary search is to:

1. Go to the middle index of an array. Check if the value is the same as the value we're looking for.
2. If the value is the same, return the index the value was found at.
3. If the value is greater than the value we're looking for, look at the half with the lower value. If the value is less than the value we're looking for, look at the half with the higher values.
   
4. Rinse & Repeat: Go to the center index of the new half and check the value.Eventually we'll have determined whether the value is in the array or absent. If absent, return -1.
   

For it, we make a binary search function which takes an array (of int's here) and returns the index where the int's value matches the value of the index of the array, or returns -1 if the value is not present in the array.
"Binary search;" what a fun little project! To discover that in only 16 iterations with a relatively small amount of instructions per iteration, it could determine the index or absence of a value in an ordered array with 100,000 members! That's... well, that's sexy!

 

// compiled & tested @ OnlineGDB
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// binary search, return index where value was found or -1 if not found.
// the std::vector<int> input should be sorted in increasing order.
int findVal(int val, std::vector<int> a){
    int len = a.size();
    if(len == 0){
        cout << "Empty array; value not present. (-1)" << endl;
        return -1; // empty array, impossible to find a value
    }
    int cur; // current index we're checking
    int lcur = 0; // left cursor. lowest index we consider still in valid range (inclusive)
    int rcur = len - 1; // right cursor; highest index in valid range (inclusive)
    cout << "\n==== starting test ====" << endl;
    int loop = 0;
    while(lcur != rcur){
        loop++;
        cout << "\nLoop # " << loop << endl;
        cout << "Cursors: [" << lcur << ", " << rcur << "]" << endl;
        cur = (( rcur - lcur ) / 2 ) + lcur; // get the center of the cursors
        cout << "cur (now " << cur << ") is ((" << rcur << " - " << lcur << ") / 2) + " << lcur << endl;
        if(a[cur] == val){
            cout << "a[" << cur << "](" << a[cur] << ") = " << val << ". done." << endl;
            return cur; // found our value. Hurray!
        }
        else if(a[cur] < val){
            lcur = cur + 1; // the value up to and including left cursor is not what we want. search rightward
            cout << "a[" << cur << "](" << a[cur] << ") < " << val << ". L-cur now " << lcur << endl;
        }
        else{
            rcur = cur - 1; // a[cur] > val. search leftward. move right cursor.
            cout << "a[" << cur << "](" << a[cur] << ") > " << val << ". R-cur now " << rcur << endl;
        }
        if(rcur < lcur){
            cout << "Right cursor is on the left side of Left cursor; error" << endl;
            return -1;
        }
        
        if(rcur < 0){
            cout << "rcur has become negative, value  not found" << endl;
            return -1; // rcur can become negative, which is an indicator we didn't find the value.
        }
    }
    // if we get here, we assume lcur == rcur
    if(a[lcur] == val){
        cout << "The last index was correct; (a[" << lcur << "] (" << a[lcur] << ") == " << val << ")" << endl;
        return lcur; // the last index to check is the correct value
    }
    else return -1;
}

int ran(int max){ // return [0,max] inclusive
    return rand() % (max+1);
}

void test(const char *name, int prelen=10, int *preA=nullptr){ // make test array and let user play with findVal()
    std::vector<int> a;
    // generate values for the vector with incrementing (sorted) values.
    int nextVal = 0;
    int len = prelen;
    if(preA == nullptr){ // make our own array
        for(int xint = 0;xint < len;xint++){ // 10 numbers that will be in order, skipping 1 or 2 numbers between each entry.
            nextVal += ran(1) + 1; // next number will be [1,2] inclusive greater than previous number
            a.push_back(nextVal);
        }
    }else{ // import pre-defined array
        for(int xint = 0;xint < len;xint++)
            a.push_back(preA[xint]);
    }
    
    cout << "\n=== Now Testing: " << name << " ===" << endl;
    while(1){
        cout << "\n\nPlease enter number to get the index (or -1) in the array.\n'q' to quit." << endl;
        if(len <= 10 && len > 0){ // can change len to big amounts. only display array if len is small
            cout << "Array: [0] = " << a[0];
            for(int xint = 1;xint < len;xint++)
                cout << ", [" << xint << "] = " << a[xint];
        }
        cout << endl << "Value to search for: ";
        std::string input = "";
        getline(cin, input);
        if(input == "q") break;
        else{
            try{
                int val = stoi(input);
                int ret = findVal(val, a);
                if(ret == -1) cout << "Could not find value '" << val << "' anywhere in the array. (-1)" << endl;
                else cout << "Found value '" << val << "' at index " << ret << " in the array." << endl;
            }catch(...){
                cout << "The entered value appears to have not been a number. Please enter a number or 'q'" << endl;
            }
        }
    }
}
int aryLen(int *ary){ // use -1 as array-terminating value
    int len = 0;
    while(ary[len] != -1) len++;
    return len;
}
int main()
{
    cout << "Starting up... " << endl;
    
    test("Normal, generated, ordered"); // 10 indices
    test("Large, generated, ordered", 100000); // 10,000 indices
    
    int t1[] = {0,1,2,3,4,5, -1}; // normal ordered array
    test("Normal ordered array", aryLen(t1), t1);
    
    int t2[] = {5,4,3,2,1,0,-1}; // reverse order array. doesn't work.
    test("Reverse ordered array", aryLen(t2), t2);
    
    int t3[] = {2,5,1,0,3,4,-1};
    test("Random, disordered array", aryLen(t3), t3); // random. doesn't work.
    
    int t4[] = {0,0,0,0,0,-1};
    test("All 0s", aryLen(t4), t4); // all zeros. Works as normal. Can only return 0 or -1.
    
    int t5[] = {0,0,0,0,1,-1};
    test("All 0s + ending 1", aryLen(t5), t5); // works normally
    
    int t6[] = {1,0,0,0,0,-1};
    test("Starting 1 + all 0s", aryLen(t6), t6); // won't work. 1 is not in ordered place
    
    test("Empty Array", 0); // works normally. Always -1
    
    cout << "Thanks, bye!" << endl;

    return 0;
}