example of binary search

Binary search is one of the most efficient search algorithms and is often used in programming. In this article, we will discuss various examples of binary search questions along with a detailed explanation of how to solve them. Let’s study together!

Definition of Binary Search

Binary search is a search algorithm that works by dividing the array in two parts that have been sorted to find the value you are looking for. This method is much more efficient than Linear Search, because each search step can eliminate half of the existing data.

requirements for using binary search

Before using binary search, there are several conditions that must be met:

1. The data must be sorted (ascending or descending)
2. data must be accessible directly (random access)
3. The data must have a structure that allows the division of two parts

Binary Search Time Complexity

Binary Search has very efficient time complexity:

• Best Case: O(1)
• Average case: O(log n)
• Worst case: O(log n)

Example#atfp_close_translate_span# Basic Level Binary Search

Example 1: Finding a number in an array

Here is an example of a simple question to understand the basic concepts of binary search:

Def binary_search(arr, target): left = 0 right = len(arr) - 1 while left <= right: MID = (Left + RIGHT) // 2 if ARR[mid] == Target: return mid elif arr[mid] < Target: Left = Mid + 1 else: Right = Mid - 1 Return -1 # Sorted Array Numbers =[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]target = 23 result = binary_search(numbers, target) print(f"number {target} found on the index {result}")

Example 2: Looking for a name in the list

Def binary_search_string(arr, target):
Left = 0
right = len(arr) - 1while left <= right:
MID = (LEFT + RIGHT) // 2
if arr[mid] == target:
MID RETURN
Elif Arr[mid] < Target:
Left = Mid + 1
Else:
Right = Mid - 1

return -1

# Sorted Name List
names = ["Andi", "Budi", "Citra", "Deni", "Eko", "Fani", "Gita"]
Target = "Eko"

Result = binary_search_string(name, target)
print(f"name {target} found on the index to-{result}")

example of intermediate level binary search questions

Example 3: Finding the Nearest Element

def find_closest(arr, target):
if len(arr) == 0:
Return Noneleft = 0
right = len(arr) - 1while left + 1 < right:
MID = (LEFT + RIGHT) // 2IF ARR[mid] == target:
RETURN ARR[mid]
Elif Arr[mid] < Target:
Left = MID
Else:
Right = Midif ABS(arr[left] - target) <= abs(arr[right] - target):
RETURN ARR[left]
RETURN ARR[right]# Sorted array
numbers = [1, 3, 6, 7, 9, 11, 14, 17]
target = 8
Result = find_closest(numbers, target)
print(f"closest value to {target} is {result}")

Example 4: Finding the Range of Values

def find_range(arr, target):
def find_first(arr, target):
Left = 0
RIGHT = LEN(ARR) - 1
First = -1while left <= right:
MID = (LEFT + RIGHT) // 2IF ARR[mid] == target:
First = MID
Right = Mid - 1
Elif Arr[mid] < Target:
Left = Mid + 1
Else:
right = mid - 1return firstdef find_last(arr, target):
Left = 0
RIGHT = LEN(ARR) - 1
Last = -1while left <= right:
MID = (LEFT + RIGHT) // 2IF ARR[mid] == target:
Last = MID
Left = Mid + 1
Elif Arr[mid] < Target:
Left = Mid + 1
Else:
Right = Mid - 1Return LastFirst = Find_First(arr, target)
Last = find_last(arr, target)
return [first, last]

# Array sorted with repeating values
numbers = [1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 6]
target = 2

Result = find_range(numbers, target)
print(f"Range value {target} is in the index {result[0]} to {result[1]}")

example of advanced binary search questions

Example 5: Binary Search on a Rotating Array

def search_rotated(arr, target):
Left = 0
right = len(arr) - 1while left <= right:
MID = (LEFT + RIGHT) // 2IF ARR[mid] == target:
return mid# check if the left side is ordered
if arr[left] <= Arr[mid]:
if arr[left] <= Target < Arr[mid]:
Right = Mid - 1
Else:
Left = Mid + 1
# the right side of the ordered
Else:
if arr[mid] < target <= arr[right]:
Left = Mid + 1
Else:
Right = Mid - 1Return -1# Sorted Array
numbers = [6, 7, 8, 1, 2, 3, 4, 5]
target = 3result = search_rotated(numbers, target)
print(f"The value of {target} found on the index to-{result}")

Example 6: Binary search to find minimum points

def find_minimum(arr):
Left = 0
right = len(arr) - 1while left  Arr[right]:
Left = Mid + 1
Else:
Right = Midreturn Arr[left]# Rotated ordered arrays
Numbers =[4, 5, 6, 7, 0, 1, 2]Result = find_minimum(numbers)
print(f"minimum value in array is {result}")

tips for doing binary search questions

1. Make sure the data is sorted
   • Before using binary search, make sure the data is sorted
   • If not sorted, sort first using the sorting algorithm
2. Identification of special conditions
   • Pay attention to whether there are special conditions such as empty arrays
   • Consider the case of an array with one element
   • Check the possibility of the target not being found
3. Avoid integer overflow
   • When calculating the middle value, use the formula: MID = LEFT + (RIGHT - LEFT) // 2
   • This method is safer than (left + right) // 2
4. Ensure termination conditions
   • Determine the correct stop condition (usually left <= right)
   • Avoid Infinite Loop by making sure the pointer is always moving

Binary Search Practice Questions

To improve understanding, try the following questions:

1. Find the first index of the target in a ordered array that has duplicates
2. Find the biggest element that is smaller than the target
3. Implement recursive binary search
4. Find the rotating point in the rotated array
5. Find two numbers in an array that is the same as the target

Conclusion

Binary search is a very efficient search algorithm with O(log n) complexity. By understanding the various problems above, you can apply binary search to solve various data search problems. The main key in using binary search is to make sure the data is sorted and identify the specific conditions that may occur.