Graphical algorithms and data structures

1. 🚀 Foreword

Yesterday more binary search, is the traditional binary search template, there are some problems, in the return of the left boundary or the right boundary of this problem, more prone to error!!

【 freehand caricature 】 Two parts of the interview to find (solution template and in-depth analysis), last time

So are there any templates that go with everything?

Take a look below!!

2. 🚀 code

Template:

// C
int lower_bound(int* nums, int numsSize, int target){
	int left = 0;
	int right = numsSize;
	while(left < right){	// The search interval [first, last] is not empty
		/ / the overflow
		int mid = left + (right - left) / 2;
		if(nums[mid] < target) left = mid + 1;
		else right = mid;
	}
	return left;			// Rightt also works, because they overlap when [left, right] is empty
}
Copy the code

# Python
def lower_bound(array, first, last, value):
	while first < last: # the search interval [first, last] is not empty
		# spill-resistant
		mid = first + (last - first) // 2
		if array[mid] < value: first = mid + 1
	    else: last = mid
	return first  		# last also works, because they overlap when [first, last) is empty
Copy the code

3. 🚀 Text

1. Whywhile(left < right)Rather thanwhile(left <= right) ?

Right = numsSize (numsSize -1); left == right;

2. Whyleft = mid + 1 和 right = mid ？

First of all, notice that we’re [left, right] left closed and right open, so the next interval is going to be [left, mid) or [mid +1, right), not -1 and +1.

3. Why are you returningleftRather thanright ？

Similarly, while terminates with the condition left == right, whichever is returned.

4. 🚀 example

• Find the minimum value in a rotation sorted array (LeetCode153)
• LeetCode: Finding the minimum value in a rotated sorted array II (LeetCode154)
• LeetCode (question 287), the drawer principle
• Illustration of LeetCode’s longest ascending subsequence (LeetCode300), greedy algorithm + binary search
• Illustration of LeetCode’s search rotation sorted array (LeetCode33), binary search
  

  

If lucky enough to help you, please help me a [praise], to a [attention]! I would appreciate an encouragement along the way.

If you want more resources, please follow @I’m Guan Xiaoliang, MAX~