Created
September 4, 2018 08:41
-
-
Save DVegasa/101e3aa6c2ac6f568bad82a778055741 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Binary search | |
* 03 Sep. 2018 | |
*/ | |
#include <iostream> | |
using namespace std; | |
int main() { | |
// 0 1 2 3 4 5 6 7 8 | |
int nums[] = {0, 1, 1, 2, 4, 5, 5, 5, 7}; | |
cout << "Ready!" << endl; | |
// Get size of array | |
int size = 0; | |
for (auto x : nums) size++; | |
// Searchable element | |
int n; | |
cin >> n; | |
int il = 0; | |
int ir = size-1; | |
if (nums[il] == n) { | |
cout << "Found (" << n << ") at " << il << " pos." << endl; | |
return 0; | |
} | |
if (nums[ir] == n) { | |
cout << "Found (" << n << ") at " << ir << " pos." << endl; | |
return 0; | |
} | |
while (true) { | |
int im = il + (ir - il) / 2; | |
cout << "il: " << il << endl; | |
cout << "im: " << im << endl; | |
cout << "ir: " << ir << endl; | |
cout << endl; | |
if (im == ir || im == il) { | |
if (n > nums[ir]) { | |
cout << "There is no this number. But it could be at the end of array" << endl; | |
break; | |
} else if (n < nums[il]) { | |
cout << "There is no this number. But it could be at start of array" << endl; | |
break; | |
} | |
cout << "There is no this number. But it could be between " << im << " and " << im + 1 << " positions" << endl; | |
break; | |
} | |
if (nums[im] == n) { | |
cout << "Found (" << n << ") at " << im << " pos." << endl; | |
break; | |
} else if (nums[im] > n) { | |
ir = im; | |
} else { // im < n | |
il = im; | |
} | |
} | |
return 0; | |
} | |
// Compiler: v.5.1.0 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment