#include <iostream>
using namespace std;
int main( ) {
const int size = 9 ;
//Bubble sort and linear search.
int anArray[ size] = { 10 ,90 ,50 ,70 ,30 ,40 ,20 ,60 ,80 } ;
int temp= 0 ;
int key;
cout << "Enter the value you would like to be the key for the linear search: " ;
cin >> key; //Key value used in linear search, this will become more valuable when we get into classes / objects
for ( int i= 0 ; i< size; i++ ) { //iterate through the loop
if ( anArray[ i] == key) { //if the value of i in the array is == to key
cout << "\n The position of " << key << " is at position " << i << " in the array." << endl << endl; //We print out where that key is in the array
break ;
}
else { //Else, we don't do anything.
//null
}
}
bool swapped= true ;
while ( swapped) {
swapped= false ;
for ( int i= 1 ; i< size; i++ ) {
if ( anArray[ i] < anArray[ i- 1 ] ) {
temp = anArray[ i] ;
anArray[ i] = anArray[ i- 1 ] ;
anArray[ i- 1 ] = temp;
swapped = true ;
}
}
}
cout << "\n \n " ;
for ( int i= 0 ; i< size; i++ ) {
cout << anArray[ i] << endl;
}
cout << "\n \n " ;
int val;
cout << "What is the value you're searching for? " ;
cin >> val;
int max= 8 , min= 0 , middle;
bool found = false ;
while ( min <= max) {
//Binary sort!
// 10,20,30,40,50,60,70,80,90
// 0 1 2 3 4 5 6 7 8
// 0 4 8
// 0 5 6 8
// 0 + 8 / 2= 4
//5 + 8 = 13 / 2 = 6.5 = 6
middle = ( ( max+ min) / 2 ) ;
if ( anArray[ middle] < val) {
min = middle+ 1 ;
cout << "\n min now equals: " << min;
//min =0 first loop middle = 4 + 1 =5
}
if ( anArray[ middle] > val) {
max = middle- 1 ;
cout << "\n max now equals: " << max;
// max =8 set it to 5 (2nd iteration looking for 60
}
if ( anArray[ middle] == val) {
cout << "The value: " << val << " Was found at array location: " << middle;
found = true ;
break ;
}
}
if ( found == false ) {
cout << "\n The value was not found." ;
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBtYWluKCl7CiAgICBjb25zdCBpbnQgc2l6ZSA9OTsKICAgIC8vQnViYmxlIHNvcnQgYW5kIGxpbmVhciBzZWFyY2guCiAgICBpbnQgYW5BcnJheVtzaXplXT17MTAsOTAsNTAsNzAsMzAsNDAsMjAsNjAsODB9OwogICAgaW50IHRlbXA9MDsKICAgIAogICAgaW50IGtleTsKICAgIGNvdXQgPDwiRW50ZXIgdGhlIHZhbHVlIHlvdSB3b3VsZCBsaWtlIHRvIGJlIHRoZSBrZXkgZm9yIHRoZSBsaW5lYXIgc2VhcmNoOiAiOwogICAgY2luID4+IGtleTsgLy9LZXkgdmFsdWUgdXNlZCBpbiBsaW5lYXIgc2VhcmNoLCB0aGlzIHdpbGwgYmVjb21lIG1vcmUgdmFsdWFibGUgd2hlbiB3ZSBnZXQgaW50byBjbGFzc2VzIC8gb2JqZWN0cwogICAgZm9yIChpbnQgaT0wOyBpPHNpemU7IGkrKyl7Ly9pdGVyYXRlIHRocm91Z2ggdGhlIGxvb3AKICAgICAgICBpZiAoYW5BcnJheVtpXSA9PSBrZXkpey8vaWYgdGhlIHZhbHVlIG9mIGkgaW4gdGhlIGFycmF5IGlzID09IHRvIGtleQogICAgICAgICAgICBjb3V0IDw8ICJcblRoZSBwb3NpdGlvbiBvZiAiIDw8IGtleSA8PCAiIGlzIGF0IHBvc2l0aW9uICIgPDwgaSA8PCAiIGluIHRoZSBhcnJheS4iPDxlbmRsIDw8ZW5kbDsgLy9XZSBwcmludCBvdXQgd2hlcmUgdGhhdCBrZXkgaXMgaW4gdGhlIGFycmF5CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICBlbHNley8vRWxzZSwgd2UgZG9uJ3QgZG8gYW55dGhpbmcuCiAgICAgICAgICAgIC8vbnVsbAogICAgICAgIH0KICAgIH0KICAgIAogICAgCiAgICBib29sIHN3YXBwZWQ9dHJ1ZTsKICAgIHdoaWxlKHN3YXBwZWQpewogICAgICAgIHN3YXBwZWQ9ZmFsc2U7CiAgICAgICAgZm9yKGludCBpPTE7IGk8c2l6ZTsgaSsrKXsKICAgICAgICAgICAgaWYgKGFuQXJyYXlbaV0gPCBhbkFycmF5W2ktMV0pewogICAgICAgICAgICAgICAgdGVtcCA9IGFuQXJyYXlbaV07CiAgICAgICAgICAgICAgICBhbkFycmF5W2ldID0gYW5BcnJheVtpLTFdOwogICAgICAgICAgICAgICAgYW5BcnJheVtpLTFdPSB0ZW1wOwogICAgICAgICAgICAgICAgc3dhcHBlZCA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBjb3V0IDw8ICJcblxuIjsKICAgIGZvciAoaW50IGk9MDsgaTxzaXplOyBpKyspewogICAgICAgIGNvdXQgPDwgYW5BcnJheVtpXSA8PCBlbmRsOwogICAgfQogICAgY291dCA8PCAiXG5cbiI7CiAgICAKICAgIAogICAgaW50IHZhbDsKICAgIGNvdXQgPDwgIldoYXQgaXMgdGhlIHZhbHVlIHlvdSdyZSBzZWFyY2hpbmcgZm9yPyAiOwogICAgY2luID4+IHZhbDsKICAgIAogICAgaW50IG1heD0gOCwgbWluPTAsIG1pZGRsZTsKICAgIGJvb2wgZm91bmQgPSBmYWxzZTsKICAgIAogICAgd2hpbGUobWluIDw9IG1heCl7CiAgICAgICAgLy9CaW5hcnkgc29ydCEKICAgICAgICAvLyAxMCwyMCwzMCw0MCw1MCw2MCw3MCw4MCw5MAogICAgICAgIC8vIDAgIDEgIDIgIDMgIDQgIDUgIDYgIDcgIDgKICAgICAgICAvLyAwICAgICAgICAgICA0ICAgICAgICAgICA4CiAgICAgICAgLy8gMCAgICAgICAgICAgICAgNSAgNiAgICAgOAogICAgICAgIAogICAgICAgIAogICAgICAgIC8vIDAgKyA4IC8gMj0gIDQKICAgICAgICAvLzUgKyA4ID0gMTMgLyAyID0gNi41ID0gNgogICAgICAgIG1pZGRsZSA9ICgobWF4K21pbikvMik7CiAgICAgICAgaWYgKGFuQXJyYXlbbWlkZGxlXSA8IHZhbCl7CiAgICAgICAgICAgIG1pbiA9IG1pZGRsZSsxOwogICAgICAgICAgICBjb3V0IDw8ICJcbm1pbiBub3cgZXF1YWxzOiAiIDw8IG1pbjsKICAgICAgICAgICAgLy9taW4gPTAgZmlyc3QgbG9vcCAgIG1pZGRsZSA9IDQgKyAxID01CiAgICAgICAgfQogICAgICAgIGlmIChhbkFycmF5W21pZGRsZV0gPiB2YWwpewogICAgICAgICAgICBtYXggPSBtaWRkbGUtMTsKICAgICAgICAgICAgY291dCA8PCJcbm1heCBub3cgZXF1YWxzOiAiPDwgbWF4OwogICAgICAgICAgICAvLyBtYXggPTggICBzZXQgaXQgdG8gNSAgKDJuZCBpdGVyYXRpb24gbG9va2luZyBmb3IgNjAKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgaWYgKGFuQXJyYXlbbWlkZGxlXSA9PSB2YWwpewogICAgICAgICAgICBjb3V0IDw8ICJUaGUgdmFsdWU6ICI8PCB2YWwgPDwgIiBXYXMgZm91bmQgYXQgYXJyYXkgbG9jYXRpb246ICAiPDwgbWlkZGxlOwogICAgICAgICAgICBmb3VuZCA9IHRydWU7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KICAgIAogICAgCiAgICAKICAgIGlmIChmb3VuZCA9PSBmYWxzZSl7CiAgICAgICAgY291dCA8PCAiXG5UaGUgdmFsdWUgd2FzIG5vdCBmb3VuZC4iOwogICAgfQogICAgCiAgICAKICAgIAogICAgCiAgICAKIApyZXR1cm4gMDsKfQo=