Binary Search
Algorithm
-
Given:
-
- array of values
-
- a target value
-
-
Find: the index for the target value
-
Precondition: The values must be presorted
Pseudo code
- Find the midpoint value
left= start indexright= end index- Loop:
middleIndex= midpoint betweenleftandright- lookup
middleValueatmiddleIndex - If:
middleValuevalue >target:- then: decrement
right
- then: decrement
- else if:
middleValue<target- then: increment
left
- then: increment
- else if
middleValue==target- then: return the index
Binary Search
Interactive graph
On this page
Algorithm
Pseudo code