FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

algorithm/Week_01/id_21/LeetCode_081_021.cpp at master · feixiangcode/algorithm · GitHub

43 lines (40 loc) · 1.07 KB

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

/*

* BF: 直接遍历，算法复杂度 O(N)

*/

class Solution {

public:

bool search(vector<int>& nums, int target) {

for(auto itr = nums.begin(); itr != nums.end(); itr++) {

if (*itr == target) return true;

}

return false;

}

};

/*

* 二分法查找

*/

class Solution {

public:

bool search(vector<int>& nums, int target) {

if (nums.size() < 1) return false;

if (nums.size() == 1) return nums[0] == target;

// 前半段，顺序查找 target

// 如果没有找到 target ，但是找到反转的位置，则停止顺序查找

int begin = 0;

while (begin + 1 < nums.size()) {

if (nums[begin] == target || nums[begin + 1] == target) return true;

if (nums[begin] > nums[begin + 1]) break;

begin++;

}

// 后半段使用二分法查找

int end = nums.size();

while (begin + 1 < end && end <= nums.size()) {

int pos = (begin + end) / 2;

if (nums[pos] == target) return true;

if (begin == end) break;

if (nums[pos] < target) begin = pos;

else end = pos;

}

return false;

}

};

Back | FazBrowse Home | New Git URL