題目描述：
輸入一個有序的數(shù)組 sort_array 和一個無序的數(shù)組 random_array 精绎，對于無序數(shù)組 random_array 中的每個元素速缨，判斷它們是否在有序數(shù)組 sort_array 中，存在標(biāo)記 1 捺典，不存在標(biāo)記 0鸟廓；
輸入：sort_array = [1,3,5,7,9,11]；random_array = [1,2,3,4,5,6,7]；
輸出：resuklt = [1,0,1,0,1,0,0]引谜；
題解：
考慮是判斷目標(biāo)元素是否存在于有序數(shù)組中牍陌，我們采用二分查找的方法進(jìn)行判斷；
對于數(shù)組 [1,3,5,7,9,11] 和目標(biāo)數(shù) target = 8 ：
begin = 0员咽；end = 5毒涧；mid = (begin + end) / 2
- 將數(shù)組分為兩部分： (1, 3), 5, (7, 9, 11)
對目標(biāo)數(shù) target 和 數(shù)組中間的數(shù) sort_array[mid] 大小進(jìn)行比較：
對于 target = 8，sort_array[mid] = 5贝室；target > sort_array[mid]契讲，所以我們?nèi)『蟀攵危?,9,11）；
begin = mid + 1 = 3滑频；end = 5捡偏；mid = (begin + end) / 2 - 將數(shù)組分為兩部分： (7), 9, (11)
對目標(biāo)數(shù) target 和 數(shù)組中間的數(shù) sort_array[mid] 大小進(jìn)行比較：
target < sort_array[mid]，所以我們?nèi)∏鞍攵危?）峡迷；
begin = 3银伟；end = mid - 1 = 3；mid = (begin + end) / 2 - 將數(shù)組分為兩部分： (), 7, ()
對目標(biāo)數(shù) target 和 數(shù)組中間的數(shù) sort_array[mid] 大小進(jìn)行比較：
target > sort_array[mid]绘搞，所以我們?nèi)『蟀攵危ǎ?br> begin = 3彤避；end = mid - 1 = 2；夯辖，此時琉预，end < begin，說明該段不存在蒿褂；所以數(shù)組中不存在目標(biāo)數(shù) 8圆米。
My Solution(C/C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> judge(vector<int> &sort_array, vector<int> &random_array) {
int begin = 0;
int end = sort_array.size() - 1;
int target;
vector<int> result;
for (int i = 0; i < random_array.size(); i++) {
target = random_array[i];
result.push_back(binary_search(begin, end, sort_array, target));
}
return result;
}
private:
bool binary_search(int begin, int end, vector<int> &sort_array, int target) {
if (begin > end) {
return false;
}
int mid = (begin + end) / 2;
if (target == sort_array[mid]) {
return true;
}
else if (target < sort_array[mid]) {
end = mid - 1;
return binary_search(begin, end, sort_array, target);
}
else if (target > sort_array[mid]) {
begin = mid + 1;
return binary_search(begin, end, sort_array, target);
}
}
};
int main() {
vector<int> sort_array;
vector<int> random_array;
sort_array.push_back(-1);
sort_array.push_back(2);
sort_array.push_back(5);
sort_array.push_back(20);
sort_array.push_back(90);
sort_array.push_back(100);
sort_array.push_back(207);
sort_array.push_back(800);
random_array.push_back(50);
random_array.push_back(90);
random_array.push_back(3);
random_array.push_back(-1);
random_array.push_back(207);
random_array.push_back(80);
Solution s;
vector<int> result;
result = s.judge(sort_array, random_array);
for (int i = 0; i < result.size(); i++) {
printf("%d ", result[i]);
}
return 0;
}
結(jié)果
1 0 1 0 1 0 1
