1. Overview of Binary Search
Binary Search is an algorithm used to find the position of a specific value in a sorted array.
It is very efficient as it divides the array in half to find the desired value,
having a time complexity of O(log n) in both average and worst cases.
This is significantly better than the O(n) of linear search.
1.1 Principle of Binary Search
Binary Search proceeds with the following steps:
- Check if the array to be searched is sorted.
- Set the start index and end index.
- Calculate the middle index.
- Compare the middle value to the value you want to find.
- If the value to be found is less than the middle value, set the end index to middle index – 1,
and if it’s greater, set the start index to middle index + 1. - Repeat until the value is found or the start index is greater than the end index.
2. Algorithm Problems
Now, let’s look at a problem that utilizes binary search.
Problem: Finding the Index of a Specific Number in an Array
Given an integer arraynumsand an integertarget, write a function that returns the index oftargetif it exists in the arraynums, or -1 if it does not exist. Example: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1
3. Problem Solving Process
To solve the problem, we will use the binary search algorithm to find the target value in the array.
I will explain step by step.
3.1 Function Definition
First, we define the binarySearch function that will perform the binary search.
This function takes the array nums and the target value as arguments.
func binarySearch(nums: [Int], target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
3.2 Variable Initialization
Initialize the variables left and right to 0 and the length of the array - 1, respectively.
left represents the starting index of the search range, and right represents the ending index.
3.3 Calculating the Middle Value
Use the while loop to repeat until left is less than or equal to right.
In each iteration, calculate the middle index mid.
When calculating the middle value, use left + (right - left) / 2 to prevent overflow.
3.4 Comparing the Target
If the middle value nums[mid] equals target, return that index mid.
If nums[mid] is less than target,
set left to mid + 1 to search the right half.
Conversely, if nums[mid] is greater than target,
set right to mid - 1 to search the left half.
3.5 Returning the Result
When the loop ends, it means target does not exist in the array, so return -1.
4. Full Code
func binarySearch(nums: [Int], target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = left + (right - left) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
// Example usage
let nums = [-1, 0, 3, 5, 9, 12]
let target = 9
let result = binarySearch(nums: nums, target: target)
print(result) // 4
5. Advantages and Disadvantages of Binary Search
5.1 Advantages
The main advantage of binary search is its fast search speed.
It shows significantly higher performance compared to linear search when dealing with very large datasets.
5.2 Disadvantages
However, a disadvantage of using binary search is that the data must be sorted.
Frequent insertion and deletion of data may require separate sorting operations.
6. Conclusion
Binary search is an efficient searching method and is one of the topics frequently asked in coding tests.
Through the above problem, I hope you have understood the principles and implementation methods of binary search,
and gained useful experience in writing code in Swift.
7. Additional Practice Problems
To deepen your understanding of binary search, try solving the additional problems below.
- Write a function that finds and returns all indices of a specific number in a given integer array.
- Implement a function that finds the first and last positions in a sorted array.
- Write a function that determines whether there is a combination of two numbers in an integer array that adds up to a specific number.