Algorithm-I, Day 1
Ch'i YU Lv3
  2022-03-06 18:37:06 2022-03-06 18:37      1 Mins  

Topic: Binary Search

Q704 Binary Search

Q278 First Bad Version

Q35 Search Insert Position

A searching algorithm which finds an element's position in a sequential(sorted) and comparable array.

In this method, the element is always searched in the middle of a portion of an array sliced in halves.

This method do follow the divide-and-conquer approach.

Iteration Method
1
2
3
4
5
6
7
8
9
10
11
## Do until the pointers L(Low/Left) and R(High/Right) meet each other,
## or do until the target element is found.
	Mid = (L + R) / 2
    if Target == Grid[Mid]
        return Mid
    else if Target > Grid[Mid]
        L = Mid + 1
    else ## Target < Grid[Mid]
    	R = Mid - 1
    
    continue
Recursion Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
## Define a function and calle itself within definition.

## Do until the pointers L(Low/Left) and R(High/Right) meet each other,
## or do until the target element is found.
RM(Grid, Target, L, R)
	if L > R
    	return Not Found
    else
    	Mid = (L + R) / 2
        if Target == Grid[Mid]
        	return Mid
        else if Target > Grid[Mid]
        	returnRM(Grid, Target, Mid + 1, R)
        else ## Target < Grid[Mid]
        	returnRM(Grid, Target, L, Mid - 1)
Time Complexities
  • Best Case Complexity: O(1)
  • Worst Case Complexity: O(log n)
  • Average Case Complexity: O(log n)
Space Complexities
  • O(1)
Footnotes

In Q278 First Bad Version:

Pointer L represents the location of the first bad version.

In Q35 Search Insert Position:

Pointer L represents the location of the target insert position.