Mock interview: binary search algorithm

Here is the gist.

	6:41
	Array - find the largest number
	Sorted in ascending order - O(1) access -
	binary search given a number logn
	Not sorted - go over each element O(N) - max
	// [1, 2, 2] - return 1 or 2, duplicate
	Int FindGivenNumber(int[] numbers, int search) // [1, 2], 2
	{
	if(numbers == null || numbers.Length == 0) // ok
	Return -1;
	// ascending order
	Var length = numbers.Length; // 2
	Var start =0; //
	Var end = length - 1; // 1
	if(search < numbers[start] || search> numbers[end]) // 2 < 1 || 2 > 2 -> false
	Return -1;
	// start <= end
	while(numbers[start] <= numbers[end]) // start = end = 1, true
	{
	var middle = start + (end - start)/ 2; // 1 = 1 + (1-1)/2 = 1
	var middleValue = numbers[middle];// numbers[1] = 2
	if(middleValue == search) // 2 == 2 true
	return middle; // 1
	if(middleValue < search) // 1 < 2 true
	start = middle + 1; // remove left half - start = 1
	else
	end = middle - 1; // remove right half
	}
	return -1;
	}
	//recursive
	Int FindGivenNumber(int[] numbers, int start, int end, int search) // [1, 2], 2
	{
	if(numbers == null || numbers.Length == 0 || start > end) //
	Return -1;
	// ascending order
	Var length = numbers.Length; // 2
	if(search < numbers[start] || search> numbers[end])
	Return -1;
	var middle = start + (end - start)/ 2;
	var middleValue = numbers[middle];
	if(middleValue == search) //
	return middle; //
	if(search > middleValue ) //
	{ start = middle +1;
	}
	else
	{
	end = middle - 1;
	}
	return FindGivenNumber( numbers, start, end, search)
	}
	what went well
	Simple question to find element in the sorted array - answer is simple and correct
	Sorted array - binary search, write code and tested and it works
	What would you do differently?
	As interviewer gave me hint, I should ask if duplicate value in sorted array, then it may be leftmost one or last one or doesn not matter
	Testing - learn how to unit test
	First, pick [1, 2] compared to [1,2,3,4]
	Good enough, I need to do step by step to show - do not skip anything
	Mix so many things, index value with array number, and then a few places as well.
	Preparation of interview - get google docs ready - prepare technical for mock interview
	Zoom - time limit
	Facebook messenger
	Skype -
	Continue to use it
	Headphone - turn off your phone ring - wechat rings - polite
	Should ask interviewer:
	all numbers in the memoary
	Sorted array, what if the number has duplicate
	and more
	Search - better to name as target
	Turn off mobile phone
	Save Google docs link to prepare for mock interview
	Do not cut the interviewer when we talk
	interviewer suggested me to use test case [1, 2], I chose [1, 2, 3, 4]
	Remove redundant code
	assume that numbers are valid - I still wrote a line to check if the number is valid
	Prepare better for interview:
	Kill all browser windows on my computer, stop stock research ;

view raw Binary search hosted with ❤ by GitHub

Actionable Item 

Follow up
June 20, 2020 10:00 PM

 Actually I found out that my code has a bug.

The statement is wrong, it can be a deadloop:

while(numbers[start] <= numbers[end])

It should be while(start <= end).

When I fixed my bug of mixing start with numbers[start], I just quickly updated while statement.

I should stay calm, and think about it before I make the change. This is a terrible mistake.

10:20 PM

while(numbers[start] <= numbers[end])

Also there is index-out-of-range error as well besides deadloop.