CODEWITHSUNDEEP
pythonpython-3.xsortingsearch2d
Zeid Tisnes
Zeid Tisnes

Reputation: 416

Search a number in a sorted 2D array

I'm trying to find the number that I'm looking from in a 2D array list. However, it has to be sorted first before searching.

Everything seems to be working fine when I'm trying to find a number in the 2D array. It is just the fact of sorting the 2D array in a way that will still be working. Let's assume I want to sort a 3x3 2D array. The way that it should display is:

    [[8, 27, 6],
     [1, 0, 11],
     [10, 9, 3]]

Then, I will be looking for a number by using the binary search method through the sorted 2D array. My mid value will be in the middle of the array from the search.

This is just an example, but what I want to accomplish when I put randomized numbers and then sort row and columns. Using this idea, I'm using the random.randint() library from Python to randomized my numbers. Then, I'm trying to sort afterward in my 2d array, but it isn't really sorting before continuing. 

n = 5
m = 5

def findnum_arr(array, num):
    low = 0
    high = n * m - 1
    while (high >= low):
        mid = (low + high) // 2
        i = mid // m
        j = mid % m

        if (num == array[i][j]):
            return True
        if (num < array[i][j]):
            high = mid - 1
        else:
            low = mid + 1
    return False

if __name__ == '__main__':
    multi_array = [[random.randint(0, 20) for x in range(n)] for y in range(m)]
    sorted(multi_array)

Sorted:

    [[0, 1, 3],
     [6, 8, 9],
     [10, 11, 27]]

Should be the sorted 2D array. Is it possible that both the row and column are sorted respectively with the sorted function?

Upvotes: 0

Views: 217

Answers (2)

Zeid Tisnes
Zeid Tisnes

Reputation: 416

Finally found out a proper solution without using numpy and avoiding sum() module.

if __name__ == '__main__':
    x = 7
    multi_array = [[random.randint(0, 200) for x in range(n)] for y in range(m)]
    # one_array = sorted(list(itertools.chain.from_iterable(multi_array))) Another way if you are using itertools
    one_array = sorted([x for row in multi_array for x in row])
    sorted_2d = [one_array[i:i+m] for i in range(0, len(one_array), n)]

    print("multi_array list is: \n{0}\n".format(multi_array))
    print("sorted 2D array: \n{0}\n".format(sorted_2d))
    if not findnum_arr(sorted_2d, x):
        print("Not Found")
    else:
        print("Found")

output:

multi_array list is:
[[40, 107, 23, 27, 42], [150, 84, 108, 191, 172], [154, 22, 161, 26, 31], [18, 150, 197, 77, 191], [96, 124, 81, 1
25, 186]]

sorted 2D array:
[[18, 22, 23, 26, 27], [31, 40, 42, 77, 81], [84, 96, 107, 108, 124], [125, 150, 150, 154, 161], [172, 186, 191, 1
91, 197]]

Not Found

I wanted to find a standard library module where I could flat the 2D array into 1D and sort it. Then, I would make a list comprehension of my 1D array and build it into a 2D array to. This sounds a lot of works but seems to work fine. Let me know if there is a better way to do it without numpy and faster :)

Upvotes: 0

Sam
Sam

Reputation: 74

Calling sorted on a nested list that is just going to sort based on the first index in the list.

Example: 

arr = [[8, 27, 6],[1, 0, 11],[10, 15, 3], [16, 12, 14], [4, 9, 13]]

is going to return

[[1, 0, 11], [4, 9, 13], [8, 27, 6], [10, 15, 3], [16, 12, 14]]

To do this way that you want, you are going to have to flatten and then reshape.

To do this, I would try introducing numpy. 

import numpy as np


a = np.array(sorted(sum(arr, [])))

#sorted(sum(arr, [])) flattens the list

b = np.reshape(a, (-1,3)).tolist()

EDITED FOR CLARITY: You can use your m and n as parameters in np.reshape. The first parameter (m) would return the number of arrays, while (n) would return the number of arrays.

The use of -1 in either parameter means that the reshaped array will be fit to return the requirements of the other parameter.

b would return 

[[0, 1, 3], [4, 6, 8], [9, 10, 11], [12, 13, 14], [15, 16, 27]]

Upvotes: 1

Related Questions